从优先队列中删除一个项目

Question

在 Python 中， heapq 模块提供了一个优先级队列。

它有插入和弹出项目的方法。

您如何从队列中删除您插入的不是最低优先级的项目？

（也欢迎使用替代的其他集合来执行此操作的替代食谱）

原文由 Will 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

The heapq module uses standard Python lists as underlying data structure, so you can just use the standard list method remove() and heapify() again after这个。请注意，这需要线性时间。

 # Create example data and heapify
a = range(10)
a.reverse()
heapq.heapify(a)
print a

# remove an element and heapify again
a.remove(5)
heapq.heapify(a)
print a

您可以使用未记录的函数 heapify._siftup() 再次提高堆化的性能，但整个过程仍然是 O(n)，因为 list.remove() 是 O(n)。

原文由 Sven Marnach 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

如果您知道要删除的项目的位置，您可以执行以下操作：

 a[k] = a.pop()
heapq.heapify(a)

第一步现在是 O(1) 时间，第二步可以通过使用未记录的数据来完成 O(log(N))。当然，如果你还没有找到 k，它仍然是 O(N)。

原文由 Stephen 发布，翻译遵循 CC BY-SA 3.0 许可协议