具有两个优先级值的优先级队列

Question

众所周知，插入优先级队列的元素具有确定其优先级的值。例如，如果我有五个元素A,B,C,D,E优先级(我们称之为优先级值priorityI(： A = 10, B = 5, C = 1, D = 3, E = 2 .但是我如何编写一个优先级队列，我可以在其中定义两个优先级值，我的意思是：如果两个元素具有相同的值 priorityI ，则值 priorityII 决定应该首先采用哪个元素，例如：

element A has priorityI = 3, and prioriotyII = 5
element B has priorityI = 3, and prioriotyII = 1

然后第一个元素 B 将首先从队列中取出。

Answer 1

从 Python2.6 开始，您可以使用 Queue.PriorityQueue。

插入到队列中的项根据其__cmp__方法进行排序，因此只需为要插入队列中的对象的类实现一个。

请注意，如果您的项由对象的元组组成，则无需为元组实现容器类，因为内置的元组比较实现可能符合您的需求，如上所述(首先弹出较低值的项目(。但是，您可能需要为其对象驻留在元组中的类实现 __cmp__ 方法。

>>> from Queue import PriorityQueue
>>> priority_queue = PriorityQueue()
>>> priority_queue.put((1, 2))
>>> priority_queue.put((1, 1))
>>> priority_queue.get()
(1, 1)
>>> priority_queue.get()
(1, 2)

编辑：正如@Blckknght所指出的，如果你的优先级队列只被单个线程使用，那么从Python2.3获得的heapq模块是首选的解决方案。如果是这样，请参考他的回答。

Answer 2

执行此操作的常用方法是使优先级值成为两个优先级的元组。Python 按字典顺序对元组进行排序，因此它首先会比较每个优先级的第一个元组项，只有当它们相等时，才会比较接下来的项。

在 Python 中建立优先级队列的常用方法是使用 heapq 模块的函数来操作列表。由于比较了整个值，我们可以简单地将两个优先级和一个值放入单个元组中：

import heapq
q = []  # the queue is a regular list
A = (3, 5, "Element A")  # our first item, a three-tuple with two priorities and a value
B = (3, 1, "Element B")  # a second item
heapq.heappush(q, A)  # push the items into the queue
heapq.heappush(q, B)
print(heapq.heappop(q)[2])  # pop the highest priority item and print its value

这将打印"Element B" .