Search code examples
pythonqueuepriority-queue

Priority queue with two priority values

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.

Solution

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