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?

Asked by Douglas Mayle

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.

Answered by Daniel Stutzbach

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

Answered by Lijo Joseph

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()
# 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"

Answered by Isaac Turner

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.

Answered by Sebastian Nielsen

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]

Answered by Than Win Hline

Post is based on https://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python