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

Question

我正在尝试实现一种算法来解决涉及从最大堆中间删除特定元素的天际线问题。我目前的做法是，maxheap.remove(index)但我必须跟进，heapify(maxheap)否则订单将被取消。我知道在 Java 中你可以使用类似 a 的东西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) 中删除它。

Answer 2

我会让每个元素都是一个带有是否忽略它的标志的数据结构。当您弹出时，如果它是一个被标记的元素，您将再次弹出。这非常简单、明显，并且不需要了解堆内部如何工作。例如，您不需要知道该元素实际位于堆中的位置即可对其进行标记。

这种方法的缺点是标记的元素会随着时间的推移而积累。有时，您可以将它们过滤掉，然后进行堆化。

如果这个解决方案不足以满足您的需求，您应该在 Python 中寻找某种 btree 实现。这将像您在 Java 中习惯的树形图一样。