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

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


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.


You can use

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

If you then want to pop elements, use:

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


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

import heapqclass 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 valuex = 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 valuesminh.heappush(12)maxh.heappush(12)minh.heappush(4)maxh.heappush(4)# fetch "top" valuesprint(minh[0], maxh[0])  # "4 12"# fetch and remove "top" valuesprint(minh.heappop(), maxh.heappop())  # "4 12"