c++ - 如何从 C++ 中的标准堆中删除任意元素？

Question

我有一些代码可以连续从堆中提取最大值的对象并对其进行处理。但是，在处理 max 期间，堆中的其他对象会受到影响，可能需要删除。大致:

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());
}

这会运行并给出正确的输出。但它非常慢:处理一个 40kb 的文件需要 2 分钟(堆的大小与文件的大小成线性关系)。无论如何，它需要更有效率。

remove 函数最终被调用了大约 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 堆不太熟悉)。有谁知道如何在不进行线性搜索的情况下执行此操作？

Answer 1

简单的方法是不删除您认为要删除的元素。相反，您将维护一个优先级队列以确定下一个最大元素和一个 std::set<HeapEntry*>删除的元素。获取最大元素时，检查它是否在已删除元素的集合中，然后将其从堆中删除，尝试下一个元素。根据可能删除的元素的数量，您可能还希望在从堆中删除元素时从已删除元素集中删除该元素。

不是从堆中移除元素，而是将它们添加到已移除元素的集合中。这样，堆元素仍然保持对数，您可能对元素集进行最多 O(n log n) 操作。

另一种选择是使用基于节点的优先级队列来有效地找到节点在堆中的位置。例如，Boost 提供了一个 Fibonacci 堆作为 Boost Graph Library 的一部分。您可以在那里跟踪元素的位置。但是，由于重新排列元素时的开销，基于节点的堆在实际问题规模上往往执行速度较慢。