python - 如何在不丢失 Python 中的堆属性的情况下删除堆中的特定元素？

Question

我正在尝试实现一种算法来解决天际线问题，该问题涉及从最大堆的中间移除特定元素。我目前的做法是 maxheap.remove(index) 但我必须跟进 heapify(maxheap) 否则订单将被取消。我知道在 Java 中您可以使用类似 treemap 的东西来做到这一点。无论如何，在 python 中有没有比调用两个单独的方法更有效的方法，每个方法都需要 O(n) 时间？

Answer 1

如果您知道该项目在堆中的位置，则从堆中删除任意项目是一个 O(log n) 操作。算法是:

Move the last item in the heap to the position that contains the item to remove.
Decrement heap count.
If the item is smaller than its parent
    bubble it up the heap
else
    sift it down the heap

主要问题是找到项目在堆中的位置。正如您所指出的，除非您维护更多信息，否则这样做是一个 O(n) 操作。

一个有效的解决方案是创建一个包含项键的字典，值是该项在堆中的索引。但是，您必须维护字典:

1. 当你向堆中插入一个项目时，添加一个字典条目
2. 当您从堆中删除一个项目时，删除字典条目
3. 每当您更改某个项目在堆中的位置时，就更新该项目在字典中的值。

有了这个字典，您就可以用 O(1) 的时间访问堆中某个项目的位置，并且可以在 O(log n) 的时间内删除它。