具有两个优先级值的优先级队列 [英] Priority queue with two priority values

问题描述

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

元素A的priorityI = 3，prioriotyII = 5元素 B 的优先级 I = 3，且优先级 II = 1

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

解决方案

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

插入队列的项目根据它们的__cmp__ 方法，因此只需为其对象要插入队列的类实现一个.

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

<预><代码>>>>从队列导入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 所指出的，如果您的优先级队列仅由单个线程使用，heapq 模块，可从 Python2.3 获得，是首选的解决方案.如果是这样，请参阅他的回答.

As it is good known, elements which are inserted to the priority queue have a value which determines its priority. For example if I have five elements A,B,C,D,E with priorities (let's call this priority values priorityI): A = 10, B = 5, C = 1, D = 3, E = 2. But how can I write a priority queue where I can define two priority values, I mean: if two elements has the same value of priorityI, then value priorityII decides which element should be taken first, like for example:

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

then first element B will be taken from the queue first.

解决方案

Starting from Python2.6, you can use Queue.PriorityQueue.

Items inserted into the queue are sorted based on their __cmp__ method, so just implement one for the class whose objects are to be inserted into the queue.

Note that if your items consist of tuples of objects, you don't need to implement a container class for the tuple, as the built in tuple comparison implementation probably fits your needs, as stated above (pop the lower value item first). Though, you might need to implement the __cmp__ method for the class whose objects reside in the tuple.

>>> 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)

EDIT: As @Blckknght noted, if your priority queue is only going to be used by a single thread, the heapq module, available from Python2.3, is the preferred solution. If so, please refer to his answer.

这篇关于具有两个优先级值的优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！