python - 创建 python 优先级队列

Question

我想在 python 中构建一个优先级队列，其中队列包含不同的字典及其优先级编号。因此，当调用“get 函数”时，优先级最高（编号最小）的字典将被拉出队列，而当调用“add 函数”时，新字典将被添加到队列中并根据其排序优先编号。

请帮忙...

提前致谢！

Answer 1

使用标准库中的 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

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]

OP 的要求显然是在实例化时operator.itemgetter('priority')用作参数（当然需要在模块顶部；-）。keyPriorityQueueimport operator

Answer 3

您可以通过向该类添加一个 dict 对象并在里面搜索它来做到这一点。