python - 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：一点内省会发现这heapify可能是在 C 中实现的，但内部函数的 C 实现没有暴露。如果性能对您很重要，那么考虑对典型数据进行一些时序测试，看看哪个是最好的。除非你有非常大的堆，否则 big-O 可能不是最重要的因素。

编辑：有人试图编辑此答案以删除对的呼叫，_siftdown并附有以下评论：

_siftdown 不是必需的。新 h[i] 保证是旧 h[i] 的孩子中最小的，它仍然大于旧 h[i] 的父级（新 h[i] 的父级）。_siftdown 将是无操作的。我必须编辑，因为我没有足够的代表来添加评论。

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

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

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

Answer 2

(a) 考虑一下为什么不想延迟删除。在很多情况下，这是正确的解决方案。

(b) 堆是一个列表。您可以按索引删除元素，就像任何其他列表一样，但是您将需要重新堆化它，因为它不再满足堆不变量。