python - how to get the max heap in python

Question

I use heapq module in python, I find I only can the min heap, even if I use reverse=True

I still get the min top heap

from heapq import *

h=[]
merge(h,key=lambda e:e[0],reverse=True)
heappush(h, (200, 1))
heappush(h, (300,2))
heappush(h, (400,3))
print(heappop(h))

I still get the result:

(200, 1)

I want to get result:

(400,3)

how to do it?

which is the smallest element. I want pop the largest emelment?

ps: this is part of question find the max and then divide into several elements and then put it back to the heap.

Answer 1

The documentation says,

Our pop method returns the smallest item, not the largest (called a “min heap” in textbooks; a “max heap” is more common in texts because of its suitability for in-place sorting).

So you cannot get a max heap directly. However, one way to get it indirectly is to push the negative of the item on the heap, then take the negative again just after you pop the item. So instead of heappush(h, (200, 1)) you execute heappush(h, (-200, -1)). And to pop and print the max item, execute

negmaxitem = heappop(h)
maxitem = (-negmaxitem[0], -negmaxitem[1])
print(maxitem)

There are other ways to get the same effect, depending on what exactly you are storing in the heap.

Note that trying h[-1] in a min-heap does not work to find the max item--the heap definition does not guarantee the max item will end up at the end of the list. nlargest should work but has time complexity of O(log(n)) to just examine the largest item in a min-heap, which defeats the purpose of the heap. My way has time complexity O(1) in the negative-heap to examine the largest item.

Answer 2

Why not use a PriorityQueue object? You can store (priority,key) tuples. One easy solution to make a max-heap would be to make priority be the opposite of key:

from Queue import PriorityQueue
pq = PriorityQueue()
for i in range(10): # add 0-9 with priority = -key
    pq.put((-i,i))
print(pq.get()[1]) # 9