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

Question

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

Answer 1

是的，有一种更有效的方法-如果您有它的索引或指针（取决于实现方法）。在

将需要删除的索引/指针上的数字替换为其最大值 child，并递归地重复该过程（将子节点替换为其最大的子节点，等等…），直到到达一个没有子节点的节点，可以很容易地将其删除。在

该算法的复杂度为O（logn）。在

{a1}

Answer 2

我会让每个元素都是一个数据结构，并有一个标志来指示是否忽略它。当你堆东西时，如果是被标记的元素，你会再次弹出。这很简单，很明显，而且不需要知道堆内部是如何工作的。例如，不需要知道元素在堆中的实际位置来标记它。在

这种方法的缺点是，标记的元素会随着时间的推移而累积。有时候你可以过滤掉它们然后恢复健康。在

如果这个解决方案不能满足您的需要，您应该在Python中寻找某种btree实现。它的行为类似于Java中常用的treemap。在

Answer 3

从堆中移除任意项是一个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）中删除它。在