What do I use for a max-heap implementation in Python?

Question

Python includes the heapq module for min-heaps, but I need a max heap. What should I use for a max-heap implementation in Python?

Solution 1

The easiest way is to invert the value of the keys and use heapq. For example, turn 1000.0 into -1000.0 and 5.0 into -5.0.

Solution 2

You can use

import heapq
listForTree = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]    
heapq.heapify(listForTree)             # for a min heap
heapq._heapify_max(listForTree)        # for a maxheap!!

If you then want to pop elements, use:

heapq.heappop(minheap)      # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap

Solution 3

The solution is to negate your values when you store them in the heap, or invert your object comparison like so:

import heapq

class MaxHeapObj(object):
  def __init__(self, val): self.val = val
  def __lt__(self, other): return self.val > other.val
  def __eq__(self, other): return self.val == other.val
  def __str__(self): return str(self.val)

Example of a max-heap:

maxh = []
heapq.heappush(maxh, MaxHeapObj(x))
x = maxh[0].val  # fetch max value
x = heapq.heappop(maxh).val  # pop max value

But you have to remember to wrap and unwrap your values, which requires knowing if you are dealing with a min- or max-heap.

MinHeap, MaxHeap classes

Adding classes for MinHeap and MaxHeap objects can simplify your code:

class MinHeap(object):
  def __init__(self): self.h = []
  def heappush(self, x): heapq.heappush(self.h, x)
  def heappop(self): return heapq.heappop(self.h)
  def __getitem__(self, i): return self.h[i]
  def __len__(self): return len(self.h)

class MaxHeap(MinHeap):
  def heappush(self, x): heapq.heappush(self.h, MaxHeapObj(x))
  def heappop(self): return heapq.heappop(self.h).val
  def __getitem__(self, i): return self.h[i].val

Example usage:

minh = MinHeap()
maxh = MaxHeap()
# add some values
minh.heappush(12)
maxh.heappush(12)
minh.heappush(4)
maxh.heappush(4)
# fetch "top" values
print(minh[0], maxh[0])  # "4 12"
# fetch and remove "top" values
print(minh.heappop(), maxh.heappop())  # "4 12"

Solution 4

The easiest and ideal solution

Multiply the values by -1

There you go. All the highest numbers are now the lowest and vice versa.

Just remember that when you pop an element to multiply it with -1 in order to get the original value again.

Solution 5

The Easiest way is to convert every element into negative and it will solve your problem.

import heapq
heap = []
heapq.heappush(heap, 1*(-1))
heapq.heappush(heap, 10*(-1))
heapq.heappush(heap, 20*(-1))
print(heap)

The output will look like:

[-20, -1, -10]

View more solutions

Comments

[Andrew McGregor]

It's also the standard solution.

[shabbychef]

uggh; total kludge. I am surprised heapq does not provide a reverse.

[ire_and_curses]

Wow. I'm amazed that this is not provided by heapq, and that there is no good alternative.

[Ishbir]

“it's all just Python code”: it depends on your Python version and installation. For example, my installed heapq.py has some code after line 309 (# If available, use C implementation) that does exactly what the comment describes.

[gatoatigrado]

yeah, inverting doesn't help if you don't have int / float's... in fact, there really doesn't need to be any sensible inverse for an order in general (take, for instance, something isomorphic to the natural numbers).

[Daniel Stutzbach]

@gatoatigrado: If you have something that doesn't easily map to int/float, you can invert the ordering by wrapping them in a class with an inverted __lt__ operator.

[temporary_user_name]

And what if you have a mix of positive and negative numbers to begin with? Then what?

[Dennis]

@Aerovistae same advice applies: invert the values (i.e. switch the sign) regardless if positive or negative to begin with.

[Ziyuan]

Looks like there are some undocumented functions for max heap: _heapify_max, _heappushpop_max, _siftdown_max, and _siftup_max.

[RayLuo]

Wow. I'm amazed that there IS such a built-in solution in heapq. But then it is totally unreasonable that it is NOT even slightly mentioned at all in the official document! WTF!

[Heberto Mayorquin]

Somehow I can't find this in Python Python 2.7.3.

[Lin Ma]

Hi Lijo, looks like _heapify_max not working for dyanamically added/removed elements? See my code from => stackoverflow.com/questions/33024215/…, your insights are appreciated. Thanks. :)

[Kevin J. Chase]

nneonneo's answer to a duplicate question provides a complete example of @DanielStutzbach's alternate solution: a wrapper class that reverses the total ordering of the contained class.

[Admin]

Well, this solution looks painstaking at first. But after implementation, it is actually pretty slick, with minimal code changed.

[noɥʇʎԀʎzɐɹƆ]

Poke. See my answer based on yours.

[Siddhartha]

Any of the pop/push functions break the max heap structure, so this method is not feasible.

[Alex Fedulov]

DO NOT USE IT. As LinMa and Siddhartha noticed, push/pop breaks the order.

[James T.]

Here's an example showing that @DanielStutzbach 's method works gist.github.com/jtara1/574e87ffa1b49ac09a892aad1620f2f7

[boh]

this is ugly, and how do you invert string?

[oerpli]

You can use it as long as you don't push new elements and use _heappop_maxto pop them

[Peter Mortensen]

An explanation would be in order.

[Sam Marinelli]

Just to state the obvious, _heapify_max etc. are private functions and therefore not part of the module's API. Use at your own risk, both with respect to functionality and forwards compatibility.

[Nimrod]

@oerpli ._heappop_max doesn't exist on my Python 2.7.15, only ._heappushpop_max and ._heapify_max for the underscore methods. Looks like the interface changed in Python 3 to include it.

[user4815162342]

The methods beginning with an underscore are private and can be removed without prior notice. Do not use them.

[Leo Ufimtsev]

It's possible, but I feel like it would slow things down a lot and use a lot of extra memory. MyInt can't really be used outside of the heap structure either. But thank you for typing up an example, it's interesting to see.

[Alex Baranowski]

Great, but most solution supports the classes/other types, and won't change actual data. The open question is if multiplying value by -1 won't change them (extremely precise float).

[Leo Ufimtsev]

Hah! One day after I commented I ran into the situation where I needed to put a custom object into a heap and needed a max heap. I actually re-googled this post and found your answer and based my solution off of it. (Custom object being a Point with x,y coordinate and lt overriding comparing distance from center). Thank you for posting this, I upvoted!

[jasonleonhard]

My answer is longer than the question. What explanation would you like to add?

[jasonleonhard]

wikipedia.org/wiki/Min-max_heap and docs.python.org/3.0/library/heapq.html might also be of some help.

[RossFabricant]

This gives the correct result but doesn't actually use a heap to make it efficient. The doc specifies that nlargest and nsmallest sort the list each time.

[Arthur S]

Unfortunately, the time complexity for this is O(MlogM) where M = len(nums), which defeats the purpose of heapq. See the implementation and comments for nlargest here -> github.com/python/cpython/blob/…

[RowanX]

Thank you for your informative comment, will make sure to check the attached link.

[Flair]

@boh your best bet is to import the private maxheap methods from heapq and implement heappush_max() yourself using those methods. Or create your own wrapper class around strings such at heapify() creates a maxheap for your custom string types.

[Flair]

Since they are private and can be removed without prior notice, you can just implement the methods yourself.

[Flair]

@AlexBaranowski. That's true, but that has been the response from the maintainer: bugs.python.org/issue27295

[Alex Baranowski]

Well maintainers have their right not to implement some functionality, but this one IMO is actually useful.

[Escape0707]

These private methods are built to support heapq.nsmallest and heapq.merge with reverse=True.

[Booboo]

Nice. I've taken this and added an optional list parameter to __init__ in which case I call heapq.heapify and also added a heapreplace method.

[Chiraz BenAbdelkader]

Surprised that no one caught this typo: MaxHeapInt --> MaxHeapObj. Otherwise, a very clean solution indeed.

[Chiraz BenAbdelkader]

Interestingly Fanchen Bao's answer to this question is very similar: stackoverflow.com/questions/8875706/…

[pablotrinidad]

Nice and simple!

[Adarsh Trivedi]

This could be a good solution for some coding round. Otherwise changing data within an application doesn't sound that great.

[Otieno Rowland]

Easiest to understand code, that needs no explanation.

[apadana]

Is this line needed? def __eq__(self, other): return self.val == other.val. I think it can also work without it.

[Isaac Turner]

@apadana Yes it is good to have - whether it is needed depends on the heapify implementation and what you want to do with your heap. We only need to define __lt__ and __eq__ to facilitate all comparisons between MaxHeapObj objects (<, <=, ==, >, >=), which may be needed when e.g. searching your heap.

[Shayan Amani]

@Siddhartha just use _heapify_max() after each push/pop then!

[Isaac Turner]

@ChirazBenAbdelkader Fanchen Bao's linked answer is using a tuple with a custom key object as first element, rather than using the custom object to wrap the elements, so slightly different. The tuple method allows passing a lambda which is cool.

[Mahesh]

@oerpli is there inbuilt method to push element into a max-heap. I tried heapq._heappush_max(heap, item) but its not working.

[oerpli]

@Mahesh You can look at the available methods here: github.com/python/cpython/blob/3.10/Lib/heapq.py

[wim]

There is some discussion on possibly making this public API in discuss.python.org/t/make-max-heap-functions-public-in-heapq‌​/…