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 (le

Solution 1:

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.

Solution 2:

The usual way to do this is to make your priority value a tuple of your two priorities. Python sorts tuples lexographically, so it first will compare the first tuple item of each priority, and only if they are equal will the next items be compared.

The usual way to make a priority queue in Python is using the heapq module's functions to manipulate a list. Since the whole value is compared, we can simply put our two priorities along with a value into a single tuple:

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

This prints "Element B".