Minheap

minheap.py

class MinHeap:
    def __init__(self):
        self._list = []
        self._cursor_idx = 0  # Points to the latest index

    def insert(self, value):
        self._list.append(value)

        parent_idx = self._get_parent_idx(self._cursor_idx)
        current_idx = self._cursor_idx

        while value < self._list[parent_idx]:
            if current_idx == 0:  # It's in root
                break

            self._swap(current_idx, parent_idx)
            current_idx = parent_idx
            parent_idx = self._get_parent_idx(current_idx)

        self._increase_cursor()

    def extract_min(self):
        min_value = self._list[0]

        self._list[0] = self._list.pop()
        self._cursor_idx -= 1

        # Trickle down
        self._min_heapify(0)

        return min_value

    def _min_heapify(self, idx):
        if self._is_leaf(idx):
            return

        left_child_idx, right_child_idx = self._get_child_idx(idx)

        does_right_child_exist = right_child_idx < self._cursor_idx

        if (does_right_child_exist and
                (self._list[left_child_idx] < self._list[idx] or
                 self._list[right_child_idx] < self._list[idx])):
            if self._list[left_child_idx] < self._list[right_child_idx]:
                self._swap(left_child_idx, idx)
                self._min_heapify(left_child_idx)
            else:
                self._swap(right_child_idx, idx)
                self._min_heapify(right_child_idx)
        elif self._list[left_child_idx] < self._list[idx]:
            self._swap(left_child_idx, idx)
            self._min_heapify(left_child_idx)


    def _is_leaf(self, idx):
        if (idx >= self._cursor_idx // 2):
            return True
        return False

    def _swap(self, idx1, idx2):
        self._list[idx1], self._list[idx2] = self._list[idx2], self._list[idx1]

    def _get_parent_idx(self, index):
        return (index - 1) // 2

    def _get_child_idx(self, index):
        offset = 2 * index
        return (offset + 1, offset + 2)

    def _increase_cursor(self):
        self._cursor_idx += 1


if __name__ == '__main__':
    minheap = MinHeap()
    minheap.insert(39)
    minheap.insert(38)
    minheap.insert(38)
    minheap.insert(38)
    minheap.insert(38)
    minheap.insert(38)
    minheap.insert(1)
    print(minheap.extract_min())
    print(minheap._list)