创建一个Python优先队列

Question

我想在Python中创建一个优先队列，这个队列里会有不同的字典，每个字典都有一个优先级数字。这样，当我调用“获取函数”时，优先级最高（数字最小）的字典会被从队列中取出来；而当我调用“添加函数”时，新的字典会被加入到队列中，并根据它的优先级数字进行排序。

请帮帮我...

提前谢谢你！

Answer 1

你可以通过在这个类里添加一个字典对象，然后在里面进行查找。

Answer 2

这是我在一些关于设计模式的讲座中通常会提到的一个附带说明：

class PriorityQueue(object):
 def __init__(self, key=lambda x: x):
   self.l = []
   self.key = key
 def __len__(self):
   return len(self.l)
 def push(self, obj):
   heapq.heappush(self.l, (self.key(obj), obj))
 def pop(self):
   return heapq.heappop(self.l)[-1]

提问者的要求显然是，在创建PriorityQueue的时候，要使用operator.itemgetter('priority')作为key参数（当然，模块的顶部需要先import operator）。

Answer 3

使用标准库中的heapq模块。

你没有说明想怎么把优先级和字典关联起来，不过这里有一个简单的实现方法：

import heapq

class MyPriQueue(object):
    def __init__(self):
        self.heap = []

    def add(self, d, pri):
        heapq.heappush(self.heap, (pri, d))

    def get(self):
        pri, d = heapq.heappop(self.heap)
        return d