Last active
September 26, 2020 03:37
-
-
Save mvoitko/b5e0b83b0a032c4da44ad2c3f276d2e1 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