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

Question

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

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

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

(也欢迎使用替代的其他集合来执行此操作的替代方法)

Answer 1

heapq 模块使用标准的 Python 列表作为底层数据结构，所以你可以只使用标准的 list 方法 remove() 和 heapify() 在此之后再次。请注意，这需要线性时间。

# 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)。