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

Question

众所周知，插入到优先级队列中的元素具有确定其优先级的值。例如，如果我有五个具有优先级的元素A,B,C,D,E (让我们称之为优先级值priorityI)：A = 10, B = 5, C = 1, D = 3, E = 2。但是，如何编写优先级队列，其中我可以定义两个优先级值，我的意思是:如果两个元素具有相同的priorityI值，那么value 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获得的赫普模块是首选的解决方案。如果是，请参考他的回答。

Answer 2

通常的方法是将优先级值作为两个优先级的一个元组。Python对元组进行词汇排序，因此它首先将比较每个优先级的第一个元组项，并且只有当它们相等时才会比较下一个项。

在Python中创建优先级队列的通常方法是使用模块的函数来操作列表。

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