Python:从堆中删除元素

Question

Python有实现堆数据结构的heapq模块，它支持一些基本操作(push，pop)。

如何在 O(log n) 中从堆中删除第 i 个元素？ heapq 甚至可以使用，还是我必须使用另一个模块？

注意，文档底部有一个示例: http://docs.python.org/library/heapq.html这提出了一种可能的方法——这不是我想要的。我希望删除元素，而不仅仅是标记为已删除。

Answer 1

您可以很容易地从堆中删除第 i 个元素:

h[i] = h[-1]
h.pop()
heapq.heapify(h)

只需将要删除的元素替换为最后一个元素并删除最后一个元素，然后重新堆化堆。这是 O(n)，如果你愿意，你可以在 O(log(n)) 中做同样的事情，但你需要调用几个内部 heapify 函数，或者更好，因为 larsmans 指出只需复制源_siftup/_siftdown 出 heapq.py 到你自己的代码中:

h[i] = h[-1]
h.pop()
if i < len(h):
    heapq._siftup(h, i)
    heapq._siftdown(h, 0, i)

请注意，在每种情况下，您都不能只执行 h[i] = h.pop() ，因为如果 i 引用最后一个元素，那将失败。如果您在特殊情况下删除最后一个元素，那么您可以结合覆盖和弹出。

请注意，根据堆的典型大小，您可能会发现仅调用 heapify 虽然理论上效率较低，但可能比重新使用 _siftup/ 更快_siftdown:稍加反射(reflection)就会发现 heapify 可能是用 C 实现的，但内部函数的 C 实现并没有暴露出来。如果性能对您很重要，那么考虑对典型数据进行一些时序测试，看看哪个是最好的。除非你有非常大的堆，否则 big-O 可能不是最重要的因素。

编辑:有人试图编辑此答案以删除对 _siftdown 的调用，并带有以下评论:

_siftdown is not needed. New h[i] is guaranteed to be the smallest of the old h[i]'s children, which is still larger than old h[i]'s parent (new h[i]'s parent). _siftdown will be a no-op. I have to edit since I don't have enough rep to add a comment yet.

他们在此评论中遗漏的是 h[-1] 可能根本不是 h[i] 的 child 。 h[i] 处插入的新值可能来自堆的完全不同的分支，因此可能需要在任一方向进行筛选。

还有评论询问为什么不使用 sort() 来恢复堆:调用 _siftup 和 _siftdown 都是 O(log n) 操作，调用 heapify 是 O(n)。调用 sort() 是一个 O(n log n) 操作。调用 sort 很可能会足够快，但对于大堆来说这是不必要的开销。

编辑以避免@Seth Bruder 指出的问题。当 i 引用结束元素时，_siftup() 调用将失败，但在这种情况下，从堆的末尾弹出一个元素不会破坏堆不变量。