在Python中插入时按值对元素进行排序的数据结构

Question

我需要一个队列结构,按插入值对元素(id,value)进行排序.此外,我需要能够删除具有最高值的元素.我不需要这种结构是线程安全的.在Java中,我想这与PriorirtyQueue相对应.

我应该在Python中使用什么结构？你能提供一个玩具的例子吗？

Answer 1

Python有类似的东西(它实际上是一个线程安全的包装器heapq):

from Queue import PriorityQueue

q = PriorityQueue()
q.put((-1, 'foo'))
q.put((-3, 'bar'))
q.put((-2, 'baz'))

而不是最大的,你可以得到最低的数字q.get():

>>> q.get()
(-3, 'bar')

如果您不喜欢底片,可以覆盖该_get方法:

class PositivePriorityQueue(PriorityQueue):
    def _get(self, heappop=max):
        return heappop(self.queue)