# A heap can be represented as a binary tree with each level filled up from up to down, and left to right.
# A Heap is not sorted, but in a minimum heap, each parent node has value less than or equal to its two children,
# and the root holds the minimum value in the heap, and vice versa for max heap
# to convert an array to a Min heap, the nodes hold the values of the array using the following rules:
# for a parent node that hold the value at position i in the array:
# the child nodes would be the values at positions: 2i+1 and 2i+2 in the array
# To get the position of the value that the parent node holds given the positions of one of the child nodes,
# parent node's value position is : floor((i-1)/2)
class MinHeap:
    def __init__(self, array):
        self.heap = self.build_heap(array)

    def build_heap(self, array):
        for index in range(len(array) // 2, 0, -1):
            self.sift_down(index, len(array) - 1, array)
        return array

    def peak(self):
        """Return the first element in the heap"""
        return self.heap[0]

    def sift_up(self, index, heap):
        """Restoring the heap property by swapping a node with its parent, and repeating the process on the parent
         until the stable root status is reached """
        parent_index = (index - 1) // 2
        while index > 0 and heap[index] < heap[parent_index]:
            self.swap(index, parent_index, heap)
            index = parent_index
            parent_index = (index - 1) // 2

    def sift_down(self, index1, index2, heap):
        left_child_index = (index1 * 2) + 1
        while left_child_index <= index2:
            # check if right child exists
            if index1 * 2 + 2 <= index2:
                right_child_index = index1 * 2 + 2
                # determine the smaller element between the right and left  child nodes
                if heap[right_child_index] < heap[left_child_index]:
                    index_to_swap = right_child_index
                else:
                    index_to_swap = left_child_index
            # otherwise, index to swap is the left child node
            else:
                index_to_swap = left_child_index
            # check is a swap is valid and update the left child index,
            # otherwise break, since the heap is already balanced
            if heap[index_to_swap] < heap[index1]:
                self.swap(index1, index_to_swap, heap)
                index1 = index_to_swap
                # update left child node index
                left_child_index = (index1 * 2) + 1
            else:  # elements are already  in the balanced state
                return

    def insert(self, value):
        """Insert a value at the end of the array"""
        self.heap.append(value)
        self.sift_up(index=len(self.heap) - 1, heap=self.heap)

    def remove(self):
        """ Swaps last leaf and root and remove last leaf from consideration, eventually repair downward."""
        #  swap the root with he last  leaf node
        self.swap(0, len(self.heap) - 1, self.heap)
        # remove the last node (since heap works after the LIFO rule, and pop is always removes the element at the top,
        # it was necessary to swap the last element  with the root (element with min value)
        removed_node = self.heap.pop()
        # # sift down to repair the heap tree to a stable status
        self.sift_down(0, len(self.heap), self.heap)
        return removed_node

    def swap(self, index1, index2, heap):
        heap[index1] = heap[index2] = heap[index2], heap[index1]
