Как удалить произвольный элемент из стандартной кучи в c ++?

У меня есть некоторый код, который непрерывно извлекает объект с максимальным значением из кучи и обрабатывает его. Однако во время обработки максимального значения другие объекты в куче затрагиваются, и, возможно, потребуется удалить их. Грубо говоря:

vector<HeapEntry*> myHeap = vector<HeapEntry*>();
fillHeap(myHeap, someData);
make_heap(myHeap.begin(), myHeap.end());
while (!myHeap.empty())
{
HeapEntry* hp = myHeap.front();
HeapEntry* neighbor = hp->getNeighbor();
if (someCondition)
{
remove(myHeap, neighbor);
}
//more processing of hp
}

И функция удаления:

void remove(vector<HeapEntry*> myHeap, HeapEntry* toRemove)
{
for (it = myHeap.begin(); it != myHeap.end(); it++)
{
if (*it == hp)
{
myHeap.erase(it);
break;
}
}
make_heap(myHeap.begin(), myHeap.end());
}

Это работает и дает правильный вывод. Но он медлителен до чертиков: 2 минуты на обработку файла размером 40 КБ (размер кучи линейный по размеру файла). В любом случае это должно быть более эффективным.

Функция удаления в итоге вызывается примерно n раз, где n — размер кучи. Таким образом, наличие этого линейного поиска делает весь алгоритм O (n ^ 2). Я думаю, что это проблема, и я считаю, что это может работать в O (n * log (n)).

Моя цель — сделать функцию удаления за O (log (n)). Что-то вроде:

• Идите прямо к целевому элементу
• Переключите его с последним элементом
• pop_heap (myHeap.begin (), myHeap.end ()); myHeap.pop_back ();
• make_heap (myHeap.begin (), myHeap.end ());

Я не совсем уверен, как это реализовать (я почти не знаком с кучей STL).
Кто-нибудь знает, как это сделать без выполнения линейного поиска?