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

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".