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

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

通常，我们可以把优先级的值设置成一个包含两个优先级的元组。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"。

Answer 2

从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模块是更好的选择。如果是这样，请参考他的回答。