What do I use for a max-heap implementation in Python?
PythonData StructuresHeapRecursive DatastructuresPython Problem Overview
Python includes the heapq module for min-heaps, but I need a max heap. What should I use for a max-heap implementation in Python?
Python Solutions
Solution 1 - 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.
Solution 2 - Python
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 then want to pop elements, use:
heapq.heappop(minheap) # pop from minheap
heapq._heappop_max(maxheap) # pop from maxheap
Solution 3 - Python
The solution is to negate your values when you store them in the heap, or invert your object comparison like so:
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)
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
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 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"
Solution 4 - Python
The easiest and ideal solution
> Multiply the values by -1
There you go. All the highest numbers are now the lowest and vice versa.
Just remember that when you pop an element to multiply it with -1 in order to get the original value again.
Solution 5 - Python
The Easiest way is to convert every element into negative and it will solve your problem.
import heapq
heap = []
heapq.heappush(heap, 1*(-1))
heapq.heappush(heap, 10*(-1))
heapq.heappush(heap, 20*(-1))
print(heap)
The output will look like:
[-20, -1, -10]
Solution 6 - Python
I implemented a max heap version of heapq and submitted it to PyPI. (Very slight change of heapq module CPython code.)
https://pypi.python.org/pypi/heapq_max/
https://github.com/he-zhe/heapq_max
Installation
pip install heapq_max
Usage
tl;dr: same as heapq module except adding ‘_max’ to all functions.
heap_max = [] # creates an empty heap
heappush_max(heap_max, item) # pushes a new item on the heap
item = heappop_max(heap_max) # pops the largest item from the heap
item = heap_max[0] # largest item on the heap without popping it
heapify_max(x) # transforms list into a heap, in-place, in linear time
item = heapreplace_max(heap_max, item) # pops and returns largest item, and
# adds new item; the heap size is unchanged
Solution 7 - Python
This is a simple MaxHeap
implementation based on heapq
. Though it only works with numeric values.
import heapq
from typing import List
class MaxHeap:
def __init__(self):
self.data = []
def top(self):
return -self.data[0]
def push(self, val):
heapq.heappush(self.data, -val)
def pop(self):
return -heapq.heappop(self.data)
Usage:
max_heap = MaxHeap()
max_heap.push(3)
max_heap.push(5)
max_heap.push(1)
print(max_heap.top()) # 5
Solution 8 - Python
I also needed to use a max-heap, and I was dealing with integers, so I just wrapped the two methods that I needed from heap
as follows:
import heapq
def heappush(heap, item):
return heapq.heappush(heap, -item)
def heappop(heap):
return -heapq.heappop(heap)
And then I just replaced my heapq.heappush()
and heapq.heappop()
calls with heappush()
and heappop()
respectively.
Solution 9 - Python
If you are inserting keys that are comparable but not int-like, you could potentially override the comparison operators on them (i.e. <= become > and > becomes <=). Otherwise, you can override heapq._siftup in the heapq module (it's all just Python code, in the end).
Solution 10 - Python
Extending the int class and overriding lt is one of the ways.
import queue
class MyInt(int):
def __lt__(self, other):
return self > other
def main():
q = queue.PriorityQueue()
q.put(MyInt(10))
q.put(MyInt(5))
q.put(MyInt(1))
while not q.empty():
print (q.get())
if __name__ == "__main__":
main()
Solution 11 - Python
Best way:
from heapq import *
h = [5, 7, 9, 1, 3]
h_neg = [-i for i in h]
heapify(h_neg) # heapify
heappush(h_neg, -2) # push
print(-heappop(h_neg)) # pop
# 9
Solution 12 - Python
Allowing you to chose an arbitrary amount of largest or smallest items
import heapq
heap = [23, 7, -4, 18, 23, 42, 37, 2, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
heapq.heapify(heap)
print(heapq.nlargest(3, heap)) # [42, 42, 37]
print(heapq.nsmallest(3, heap)) # [-4, -4, 2]
Solution 13 - Python
I have created a heap wrapper that inverts the values to create a max-heap, as well as a wrapper class for a min-heap to make the library more OOP-like. Here is the gist. There are three classes; Heap (abstract class), HeapMin, and HeapMax.
Methods:
isempty() -> bool; obvious
getroot() -> int; returns min/max
push() -> None; equivalent to heapq.heappush
pop() -> int; equivalent to heapq.heappop
view_min()/view_max() -> int; alias for getroot()
pushpop() -> int; equivalent to heapq.pushpop
Solution 14 - Python
To elaborate on https://stackoverflow.com/a/59311063/1328979, here is a fully documented, annotated and tested Python 3 implementation for the general case.
from __future__ import annotations # To allow "MinHeap.push -> MinHeap:"
from typing import Generic, List, Optional, TypeVar
from heapq import heapify, heappop, heappush, heapreplace
T = TypeVar('T')
class MinHeap(Generic[T]):
'''
MinHeap provides a nicer API around heapq's functionality.
As it is a minimum heap, the first element of the heap is always the
smallest.
>>> h = MinHeap([3, 1, 4, 2])
>>> h[0]
1
>>> h.peek()
1
>>> h.push(5) # N.B.: the array isn't always fully sorted.
[1, 2, 4, 3, 5]
>>> h.pop()
1
>>> h.pop()
2
>>> h.pop()
3
>>> h.push(3).push(2)
[2, 3, 4, 5]
>>> h.replace(1)
2
>>> h
[1, 3, 4, 5]
'''
def __init__(self, array: Optional[List[T]] = None):
if array is None:
array = []
heapify(array)
self.h = array
def push(self, x: T) -> MinHeap:
heappush(self.h, x)
return self # To allow chaining operations.
def peek(self) -> T:
return self.h[0]
def pop(self) -> T:
return heappop(self.h)
def replace(self, x: T) -> T:
return heapreplace(self.h, x)
def __getitem__(self, i) -> T:
return self.h[i]
def __len__(self) -> int:
return len(self.h)
def __str__(self) -> str:
return str(self.h)
def __repr__(self) -> str:
return str(self.h)
class Reverse(Generic[T]):
'''
Wrap around the provided object, reversing the comparison operators.
>>> 1 < 2
True
>>> Reverse(1) < Reverse(2)
False
>>> Reverse(2) < Reverse(1)
True
>>> Reverse(1) <= Reverse(2)
False
>>> Reverse(2) <= Reverse(1)
True
>>> Reverse(2) <= Reverse(2)
True
>>> Reverse(1) == Reverse(1)
True
>>> Reverse(2) > Reverse(1)
False
>>> Reverse(1) > Reverse(2)
True
>>> Reverse(2) >= Reverse(1)
False
>>> Reverse(1) >= Reverse(2)
True
>>> Reverse(1)
1
'''
def __init__(self, x: T) -> None:
self.x = x
def __lt__(self, other: Reverse) -> bool:
return other.x.__lt__(self.x)
def __le__(self, other: Reverse) -> bool:
return other.x.__le__(self.x)
def __eq__(self, other) -> bool:
return self.x == other.x
def __ne__(self, other: Reverse) -> bool:
return other.x.__ne__(self.x)
def __ge__(self, other: Reverse) -> bool:
return other.x.__ge__(self.x)
def __gt__(self, other: Reverse) -> bool:
return other.x.__gt__(self.x)
def __str__(self):
return str(self.x)
def __repr__(self):
return str(self.x)
class MaxHeap(MinHeap):
'''
MaxHeap provides an implement of a maximum-heap, as heapq does not provide
it. As it is a maximum heap, the first element of the heap is always the
largest. It achieves this by wrapping around elements with Reverse,
which reverses the comparison operations used by heapq.
>>> h = MaxHeap([3, 1, 4, 2])
>>> h[0]
4
>>> h.peek()
4
>>> h.push(5) # N.B.: the array isn't always fully sorted.
[5, 4, 3, 1, 2]
>>> h.pop()
5
>>> h.pop()
4
>>> h.pop()
3
>>> h.pop()
2
>>> h.push(3).push(2).push(4)
[4, 3, 2, 1]
>>> h.replace(1)
4
>>> h
[3, 1, 2, 1]
'''
def __init__(self, array: Optional[List[T]] = None):
if array is not None:
array = [Reverse(x) for x in array] # Wrap with Reverse.
super().__init__(array)
def push(self, x: T) -> MaxHeap:
super().push(Reverse(x))
return self
def peek(self) -> T:
return super().peek().x
def pop(self) -> T:
return super().pop().x
def replace(self, x: T) -> T:
return super().replace(Reverse(x)).x
if __name__ == '__main__':
import doctest
doctest.testmod()
https://gist.github.com/marccarre/577a55850998da02af3d4b7b98152cf4
Solution 15 - Python
The heapq module has everything you need to implement a maxheap. It does only the heappush functionality of max-heap. I've demonstrated below how to overcome that below ⬇
Add this function in the heapq module:
def _heappush_max(heap, item):
"""Push item onto heap, maintaining the heap invariant."""
heap.append(item)
_siftdown_max(heap, 0, len(heap)-1)
and at the end add this :
try:
from _heapq import _heappush_max
except ImportError:
pass
Voila ! It's done.
PS - to go to heapq function . first write " import heapq" in your editor and then right click 'heapq' and select go to defintion.
Solution 16 - Python
In case if you would like to get the largest K element using max heap, you can do the following trick:
nums= [3,2,1,5,6,4]
k = 2 #k being the kth largest element you want to get
heapq.heapify(nums)
temp = heapq.nlargest(k, nums)
return temp[-1]
Solution 17 - Python
Following up to Isaac Turner's excellent answer, I'd like put an example based on K Closest Points to the Origin using max heap.
from math import sqrt
import heapq
class MaxHeapObj(object):
def __init__(self, val):
self.val = val.distance
self.coordinates = val.coordinates
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)
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 peek(self):
return heapq.nsmallest(1, self.h)[0].val
def __getitem__(self, i):
return self.h[i].val
class Point():
def __init__(self, x, y):
self.distance = round(sqrt(x**2 + y**2), 3)
self.coordinates = (x, y)
def find_k_closest(points, k):
res = [Point(x, y) for (x, y) in points]
maxh = MaxHeap()
for i in range(k):
maxh.heappush(res[i])
for p in res[k:]:
if p.distance < maxh.peek():
maxh.heappop()
maxh.heappush(p)
res = [str(x.coordinates) for x in maxh.h]
print(f"{k} closest points from origin : {', '.join(res)}")
points = [(10, 8), (-2, 4), (0, -2), (-1, 0), (3, 5), (-2, 3), (3, 2), (0, 1)]
find_k_closest(points, 3)
Solution 18 - Python
there's build in heap in python ,but I just want to share this if anyone want to build it by himself like me . I'm newbie in python don't judge if i made i mistake . algorithm is working but about the efficiency i don't know
class Heap :
def __init__(self):
self.heap = []
self.size = 0
def add(self, heap):
self.heap = heap
self.size = len(self.heap)
def heappush(self, value):
self.heap.append(value)
self.size += 1
def heapify(self, heap ,index=0):
mid = int(self.size /2)
"""
if you want to travel great value from bottom to the top you need to repeat swaping by the hight of the tree
I don't how how can i get the height of the tree that's why i use sezi/2
you can find height by this formula
2^(x) = size+1 why 2^x because tree is growing exponentially
xln(2) = ln(size+1)
x = ln(size+1)/ln(2)
"""
for i in range(mid):
self.createTee(heap ,index)
return heap
def createTee(self, heap ,shiftindex):
"""
"""
"""
this pos reffer to the index of the parent only parent with children
(1)
(2) (3) here the size of list is 7/2 = 3
(4) (5) (6) (7) the number of parent is 3 but we use {2,1,0} in while loop
that why a put pos -1
"""
pos = int(self.size /2 ) -1
"""
this if you wanna sort this heap list we should swap max value in the root of the tree with the last
value in the list and if you wanna repeat this until sort all list you will need to prevent the func from
change what we already sorted I should decrease the size of the list that will heapify on it
"""
newsize = self.size - shiftindex
while pos >= 0 :
left_child = pos * 2 + 1
right_child = pos * 2 + 2
# this mean that left child is exist
if left_child < newsize:
if right_child < newsize:
# if the right child exit we wanna check if left child > rightchild
# if right child doesn't exist we can check that we will get error out of range
if heap[pos] < heap[left_child] and heap[left_child] > heap[right_child] :
heap[left_child] , heap[pos] = heap[pos], heap[left_child]
# here if the righ child doesn't exist
else:
if heap[pos] < heap[left_child] :
heap[left_child] , heap[pos] = heap[pos], heap[left_child]
# if the right child exist
if right_child < newsize :
if heap[pos] < heap[right_child] :
heap[right_child], heap[pos] = heap[pos], heap[right_child]
pos -= 1
return heap
def sort(self ):
k = 1
for i in range(self.size -1 ,0 ,-1):
"""
because this is max heap we swap root with last element in the list
"""
self.heap [0] , self.heap[i] = self.heap[i], self.heap[0]
self.heapify(self.heap ,k)
k+=1
return self.heap
h = Heap()
h.add([5,7,0,8,9,10,20,30,50,-1] )
h.heappush(-2)
print(" before heapify ")
print(h.heap)
print(" after heapify ")
print(h.heapify(h.heap,0))
print(" after sort ")
print(h.sort())
Output :
before heapify [5, 7, 0, 8, 9, 10, 20, 30, 50, -1, -2]
after heapify [50, 30, 20, 8, 9, 10, 0, 7, 5, -1, -2]
after sort [-2, -1, 0, 5, 7, 8, 9, 10, 20, 30, 50]
I hope you understand my code . if there's something you don't understand put a comment I will try to help
Solution 19 - Python
arr = [3,4,5,1,2,3,0,7,8,90,67,31,2,5,567]
# max-heap sort will lead the array to assending order
def maxheap(arr,p):
for i in range(len(arr)-p):
if i > 0:
child = i
parent = (i+1)//2 - 1
while arr[child]> arr[parent] and child !=0:
arr[child], arr[parent] = arr[parent], arr[child]
child = parent
parent = (parent+1)//2 -1
def heapsort(arr):
for i in range(len(arr)):
maxheap(arr,i)
arr[0], arr[len(arr)-i-1]=arr[len(arr)-i-1],arr[0]
return arr
print(heapsort(arr))
try this