Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 644
Layla Avatar asked Oct 18 '14 15:10

Layla


People also ask

How do you reverse a priority queue in Python?

Reverse priority queue order To reverse the order of a priority queue, sort the queue using the sorted() method and set the reverse argument to True. By default, the queue is sorted in ascending order.

How do I get my priority queue in reverse order?

In Java, Priority Queue, by default implement min Priority Queue, If we need to change the order of Priority Queue from min to max Priority Queue, then we use some methods as follows: Using default Comparator Collections. reverseOrder() Using custom Comparator.

Can priority queue have duplicates Python?

Yes, in C++ priority_queue, we may have duplicate values.

Is there a priority queue in Python?

Python provides a built-in implementation of the priority queue data structure. Since the queue. PriorityQueue class needs to maintain the order of its elements, a sorting mechanism is required every time a new element is enqueued. Python solves this by using a binary heap to implement the priority queue.


1 Answers

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]
like image 77
thefourtheye Avatar answered Sep 29 '22 12:09

thefourtheye