从优先级队列中删除项目 [英] Removing an item from a priority queue

问题描述

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

In Python, the heapq module provides a priority queue.

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

It has methods for inserting and popping items.

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

How do you remove an item that you have inserted that is not the lowest priority from the queue?

（另请参阅使用替代其他集合的其他配方也欢迎）

(Alternative recipes for doing this using alternative other collections are welcome too)

推荐答案

heapq 模块使用标准的Python列表作为底层数据结构，所以你可以使用标准的列表方法 remove（）和 heapify（）

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 this. Note that this will need linear time though.

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

You could improve the performance of heapifying again by using the undocumented function heapify._siftup(), but the whole process will still be O(n) since list.remove() is O(n).

这篇关于从优先级队列中删除项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！