Layla Layla - 3 months ago 15
Python Question

how to reverse a priority queue in Python without using classes?

I am just learning the priority queues in Python, and I have made the following code:

def main():
q=Queue.PriorityQueue()
while True:
n=input("numbre?")
if n==0:
break
else:
q.put(n)
print n

while not q.empty():
print q.get()


when I input data like: 9, 1, 4, 5

it prints 1,4,5,9 which it seems correct, but I would like to know how can I do to deque in reverse order, I mean: 9,5,4,1

I know how to do that with a class, but in this case it seems the following extra code:

def __cmp__():
-cmp(q.get(),q.get())


does not work, any help?

Answer

The common pattern is to insert the data, as a tuple, along with the priority. So, you can simply change the put like this

q.put((-n ,n))

So, when the tuples are compared, if the numbers are 9, 1, 4 and 5, they will be compared like this (-9, 9), (-1, 1), (-4, 4) and (-5, 5). Since, -9 is the smallest of all, it will be retrieved first and then -5 and then -4 and then -1.

Example:

from Queue import PriorityQueue
numbers, Q = [9, 1, 4, 5], PriorityQueue()
for number in numbers:
    Q.put((-number, number))

while not Q.empty():
    print Q.get()

Output

(-9, 9)
(-5, 5)
(-4, 4)
(-1, 1)

To get only the actual value, just print only the second element, like this

while not Q.empty():
    print Q.get()[1]