In Python, what do I use for a max-heap implementation?

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 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 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.

element must be multiplied by -1 in order to return to 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]
``````