Min heap Python implementation

heap.py

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)