2

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.

Ziva
  • 3,181
  • 15
  • 48
  • 80
  • whats the question? But can I write a priority queue where I can define two priority values? yes of coarse why couldnt you... – Joran Beasley Aug 10 '14 at 20:32
  • @JoranBeasley Well, I think I wrongly defined the question, it should be : If someone can show an example how can I define this type of priority queue? – Ziva Aug 10 '14 at 20:40

2 Answers2

5

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.

Community
  • 1
  • 1
Yoel
  • 9,144
  • 7
  • 42
  • 57
  • 3
    The `Queue` module (renamed `queue` in Python 3) is intended for synchronized communication between multiple threads, not as a general purpose data structure. If your priority queue is only going to be used by a single thread, you should use the `heapq` module instead (which uses a `list` to hold the data). It's what `Queue.PriorityQueue` uses internally, so you might as we get it without the synchronization related overhead! – Blckknght Aug 10 '14 at 22:37
  • @Blcknght, I wasn't familiar with `heapq`. I edited my answer to reflect your comment and upvoted your comment and your answer as well. – Yoel Aug 10 '14 at 23:58
4

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

Blckknght
  • 100,903
  • 11
  • 120
  • 169