-
-
Save Dinesh-3/95ef746835e2f48fe0b89565a085786b to your computer and use it in GitHub Desktop.
Min heap Python implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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