7

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

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 堆几乎不熟悉）。有谁知道如何在不进行线性搜索的情况下做到这一点？

4

4 回答 4

5

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

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

另一种选择是使用基于节点的优先级队列来有效地找到节点在堆中的位置。例如，Boost 提供了一个斐波那契堆作为 Boost Graph Library 的一部分。您可以在那里跟踪元素的位置。然而，基于节点的堆在实际问题大小上往往执行较慢，因为它们在重新排列元素时会产生开销。

于 2012-09-24T19:36:01.707 回答
2

感谢你的回复。我决定采用一种实际上在 HeapEntries 不再有效时删除它们的方法。实际上，我尝试向 HeapEntry 添加一个有效标志，我认为如果不是因为我已经修复了一些其他错误，这会起作用。无论如何，这就是我最终解决它的方式。

重申一下，我需要能够从堆中删除一个元素，只需一个指向该元素的指针。问题是，指针没有告诉我任何关于位置的信息堆中的元素。因此，我决定存储位置，在元素移动时保持更新，并编写一个函数从给定位置的堆中删除。简单来说，堆存储为数组，元素的位置定义了父子关系。元素的父元素应位于位置 floor((myPos - 1) / 2)，其子元素应位于位置 2*myPos+1 和 2*myPos+2。我意识到我可以编写一个 remove(position) 函数，并且在交换元素以维护堆属性的同时，也可以交换它们存储的位置。这是结果的链接，它将执行速度提高了 5 或 10 倍：

https://github.com/yankrasny/CC-Heap-with-random-delete

于 2012-11-04T20:42:56.330 回答
1

The stl philosophy is to reflect on your algorithm first, and then choose your data structure. Your're doing it the other way around.

If you plan to remove elements from your data structure in a 'random' order, you're probably better with a priority_queue or even a linked list. (Be careful, though: iterators may be invalidated after removing from some stl containers).

于 2012-09-24T18:55:42.313 回答
1

我已经晚了将近 7 年，但希望它能对其他人有所帮助。上面已经讨论了一些不错的选择，我想再添加一个。

如果您使用平衡的 BST（即set<HeapEntry*>），您可以在 O(log n) 中找到最大值并删除一个元素。这将使你的整个算法 O(n log n)。

注意 1：如果您有重复项，请multiset改为使用并删除使用<ms>.erase(<ms>.find(<obj>))以仅删除一次出现的<obj>. <ms>.erase(<obj>)删除所有出现的<obj>.

注意 2：使用以下事实可以使 find max 变为 O(1)：如果删除了一个元素，则所有迭代器、指针和对其他元素的引用仍然有效（source）。如果需要，您将迭代器缓存到最大元素并为每次插入或删除更新它。

于 2019-06-13T06:25:24.100 回答