如何在Python中删除堆中的特定元素而不丢失堆属性？

Question

我正在尝试实现一个算法来解决skyline问题，该问题涉及从max堆的中间移除特定元素。我目前的做法是maxheap.remove(index)，但我必须继续使用heapify(maxheap)，否则订单将被取消。我知道在java中，您可以使用treemap这样做。在python中有没有比调用两个单独的方法更有效的方法呢？在

Answer 1

从堆中移除任意项是一个O（logn）操作，前提是您知道该项在堆中的位置。算法是：

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（logn）中删除它。在