How to use Queue.PriorityQueue as maxheap python

Question

How to use Queue.PriorityQueue as maxheap python?

The default implementation of Queue.PriorityQueue is minheap, in the documentation also there is no mention whether this can be used or not for maxheap.

Can someone tell whether it is possible to use Queue.PriorityQueue as maxheap or not

try read this [link](http://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python) — minji, Dec 19 '16 at 08:56
One easy way would be to invert the priority. That is, if your item's priority is 2, change it to -2. — Jim Mischel, Dec 19 '16 at 14:19

score 6 · Answer 1 · answered Aug 10 '18 at 03:48

PriorityQueue by default, only support minheaps.

One way to implement max_heaps with it, could be,

# Max Heap
class MaxHeapElement(object):

    def __init__(self, x):
        self.x = x

    def __lt__(self, other):
        return self.x > other.x

    def __str__(self):
        return str(self.x)


max_heap = PriorityQueue()

max_heap.put(MaxHeapElement(10))
max_heap.put(MaxHeapElement(20))
max_heap.put(MaxHeapElement(15))
max_heap.put(MaxHeapElement(12))
max_heap.put(MaxHeapElement(27))

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

score 2 · Answer 2 · answered Jun 12 '20 at 16:37

Yes, it is possible.

Let's say you have a list:

k = [3,2,6,4,9]

Now, let's say you want to print out the max element first(or any other element with the maximum priority). Then the logic is to reverse the priority by multiplying it with -1, then use the PriorityQueue class object which supports the min priority queue for making it a max priority queue.

For example:

k = [3,2,6,4,9]
q = PriorityQueue()
for idx in range(len(k)):
    # We are putting a tuple to queue - (priority, value)
    q.put((-1*k[idx], idx))

# To print the max priority element, just call the get()
# get() will return tuple, so you need to extract the 2nd element
print(q.get()[1]

NB: Library is queue.PriorityQueue in Python3

score 1 · Answer 3 · answered Aug 24 '18 at 01:44

Based on the comments, the simplest way to get maxHeap is to insert negative of the element.

max_heap = PriorityQueue()

max_heap.put(MaxHeapElement(-10))
max_heap.put(MaxHeapElement(-20))
max_heap.put(MaxHeapElement(-15))
max_heap.put(MaxHeapElement(-12))
max_heap.put(MaxHeapElement(-27))

while not max_heap.empty():
    print(-1*max_heap.get())

score 0 · Answer 4 · answered Jun 04 '21 at 09:18

Invert the value of the keys and use heapq. For example, turn 1000.0 into -1000.0 and 5.0 into -5.0.

from heapq import heappop, heappush, heapify

heap = []
heapify(heap)

heappush(heap, -1 * 1000)
heappush(heap, -1 * 5)
-heappop(heap) # return 1000
-heappop(heap) # return 5

score 0 · Answer 5 · answered Jul 30 '23 at 21:42

@Kusharga has an elegant answer above. To adhere to the (priority, value) structure for an element in a priority queue, the wrapper class can be modified as below:

class MaxHeapElement(object):

   def __init__(self, priority, value):
       self.priority = priority
       self.value = value

   def __lt__(self, other):
       return self.priority > other.priority

   def __str__(self):
       return f"{self.priority}, {self.value}"

How to use Queue.PriorityQueue as maxheap python

5 Answers5