Skip to content

Instantly share code, notes, and snippets.

@mvoitko
Last active September 26, 2020 03:37
Show Gist options
  • Save mvoitko/b5e0b83b0a032c4da44ad2c3f276d2e1 to your computer and use it in GitHub Desktop.
Save mvoitko/b5e0b83b0a032c4da44ad2c3f276d2e1 to your computer and use it in GitHub Desktop.
Min heap Python implementation
from typing import List, Optional, Set, Tuple
class Heap:
def __init__(self, arr: Optional[List[int]] = None):
self._to_delete: Set[int] = set()
if arr:
self.__heapify(arr)
else:
self.__arr: List[int] = []
def __sift_down(self, i: int = 0) -> None:
len_ = len(self)
start = i
item = self.__arr[i]
# Bubble up the smaller child until hitting a leaf.
left: int = 2*i + 1 # leftmost child position
min_ = left
while left < len_:
# Set childpos to index of smaller child.
right = left + 1 # rightmost child position
if right < len_ and self.__arr[right] < self.__arr[left]:
min_ = right
# Move the smaller child up.
self.__arr[i] = self.__arr[min_]
i = min_
left: int = 2*i + 1
# The leaf at pos is empty now. Put newitem there, and bubble it up
# to its final resting place (by sifting its parents down).
self.__arr[i] = item
self.__sift_up(i, start)
def __alt_sift_down(self, i: int = 0):
"""More understandable sift down implemention"""
len_: int = len(self)
left: int = 2*i + 1 # leftmost child position
while left < len_:
right: int = left + 1 # rightmost child position
# Set min_ position to element index
min_ = i
# Set min_ position to index of min of left and element
if self.__arr[left] < self.__arr[min_]:
min_ = left
# Set min_ position to index of min of right and element
if right < len_ and self.__arr[right] < self.__arr[min_]:
min_ = right
# Finish iterating if element is minimum
if min_ == i:
break
# Move the smaller element up.
self.__arr[i], self.__arr[min_] = self.__arr[min_], self.__arr[i]
i = min_
left = 2*i + 1
def __sift_up(self, i: int, s: int = 0):
# 'heap' is a heap at all indices >= s, except possibly for pos.
# pos is the index of a leaf with a possibly out-of-order value. Restore the
# heap invariant.
ip = (i - 1) >> 1
while (i > s) and (self.__arr[i] < self.__arr[ip]):
self.__arr[i], self.__arr[ip] = self.__arr[ip], self.__arr[i]
i = ip
ip = (i - 1) >> 1
def push(self, val: int) -> None:
"""Push item onto heap, maintaining the heap invariant."""
self.__arr.append(val)
self.__sift_up(len(self)-1)
def pop(self) -> int:
"""Return and remove minimum value from heap in O(logn)"""
last = self.__arr.pop()
if len(self):
min_: int = self.__arr[0]
self.__arr[0] = last
self.__sift_down()
return min_
return last
def remove(self, val: int) -> None:
self._to_delete.add(val)
@property
def min(self) -> int:
return self.__arr[0]
def __heapify(self, arr: List[int]) -> List[int]:
"""Transform list into a heap, in-place, in O(len(arr)) time."""
self.__arr = arr
n = len(self)
# Transform bottom-up.
# The largest index there's any point to looking at is the largest with a child index in-range,
# so must have 2*i + 1 < n, or i < (n-1)/2.
# If n is even = 2*j, this is (2*j-1)/2 = j-1/2
# so j-1 is the largest, which is n//2 - 1.
# If n is odd = 2*j+1, this is (2*j+1-1)/2 = j
# so j-1 is the largest, and that's again n//2-1.
for i in reversed(range(n//2)):
self.__sift_up(i)
def __len__(self) -> int:
return len(self.__arr)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment