The Python Oracle

how to get the max heap in python

This video explains
how to get the max heap in python

--

Become part of the top 3% of the developers by applying to Toptal
https://topt.al/25cXVn

--

Track title: CC E Schuberts Piano Sonata D 784 in A

--

Chapters
00:00 Question
00:50 Accepted answer (Score 16)
02:12 Answer 2 (Score 6)
02:39 Thank you

--

Full question
https://stackoverflow.com/questions/4825...

Accepted answer links:
[The documentation]: https://docs.python.org/3/library/heapq....

--

Content licensed under CC BY-SA
https://meta.stackexchange.com/help/lice...

--

Tags
#python #heap #maxheap

#avk47



ACCEPTED ANSWER

Score 17


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

Score 6


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