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?
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.
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.
Yes, in C++ priority_queue, we may have duplicate values.
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.
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]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With