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?

Asked by Douglas Mayle

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.

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.

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