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

Problem

For min-heaps, Python has the heapq module, but I need a max heap. In Python, what should I use for a max-heap implementation?

Solution #1

The simplest method is to invert the keys’ values and utilize heapq. Change 1000.0 to -1000.0 and 5.0 to -5.0, for example.

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 want to make elements stand out, use:

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

Solution #3

The solution is to save your values in the heap as negated values, or invert your object comparison as follows:

``````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)
``````

The following is an 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
``````

However, you must remember to wrap and unwrap your data, which necessitates understanding whether you’re working with a min- or max-heap.

Adding classes for MinHeap and MaxHeap objects can make your code easier to understand:

``````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()
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

So there you have it. All of the highest numbers are now the lowest, and the reverse is true.

Just remember that when you pop an element, you must multiply it by -1 to retrieve the original value.

Solution #5

Converting each element to a negative value is the simplest way to address your problem.

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

The following is an example of the output:

``````[-20, -1, -10]
``````