class Min_Heap:
    # Constructor
    def __init__(self):
        self.heap = []


    # Return i's parent's index
    def _parent_index(self, i):
        return (i-1)//2


    # Return i's left child's index
    def _left_index(self, i):
        return 2*i + 1


    # Return i's right child's index
    def _right_index(self, i):
        return 2*i + 2


    # Swap two given nodes
    def _swap(self, a_index, b_index):
        temp = self.heap[a_index]
        self.heap[a_index] = self.heap[b_index]
        self.heap[b_index] = temp


    # Get minimum node
    def get_min(self):
        return self.heap[0]


    # Insert a node by appending it to end and then swapping with parents till appropriate
    def insert(self, node):
        # Append node to end
        self.heap.append(node)

        # Loop only till root node
        i = len(self.heap) - 1
        while i > 0:
            # Get parent
            parent_index = self._parent_index(i)

            # Swap if necessary, else we're done so return
            if self.heap[parent_index] > node: self._swap(i, parent_index)
            else: return


            # Move pointer to parent
            i = parent_index


    # Extract the min node
    def extract_min(self):
        # Overwrite min node with last node and delete the last node
        self.heap[0] = self.heap[-1]
        del self.heap[-1]

        # Swap with smaller child till a left child doesn't exist (i.e. we've reached the end of complete binary tree)
        i = 0
        while self._left_index(i) < len(self.heap):
            # Get children
            left_index = self._left_index(i)
            right_index = self._right_index(i)

            # Return if we've already reached appropriate place
            if self.heap[i] <= self.heap[left_index] and self.heap[i] <= self.heap[right_index]:
                return
            else:
                # Swap with appropriate child
                if self.heap[left_index] < self.heap[right_index]:
                    self._swap(i, left_index)
                    i = left_index
                else:
                    self._swap(i, right_index)
                    i = right_index