class PriorityQueue:
    """A priority queue implemented using a min heap. """
    def __init__(self):
        '''A new empty Heap.'''
        self.heap = []
    
    def is_empty(self):
        '''Return whether I am empty.'''
        return len(self.heap) == 0 
    
    def insert(self, v):
        '''Add v to me in heap order.'''
        self.heap.append(v)

        # The index of the item that was just inserted.
        i = len(self.heap) - 1

        # Bubble the new item up.
        self._percUp(i)

        
    def _percUp(self, i):
        ''' 
        Percolate an item upwards in the heap to its correct position, 
        starting at the i'th item.
        ''' 
        while i > 0 and self.heap[i] < self.heap[(i - 1) / 2]:
            self._swap(i, (i - 1) / 2)
            i = (i - 1) / 2

    def extractMin(self):
        '''Remove and return the smallest item.'''
        res = self.heap[0]
        new_top = self.heap.pop()

        if len(self.heap) != 0:
            # Move the last item to the top so we can keep the heap shape.
            self.heap[0] = new_top
            # Bubble the new top item down into place.
            self._percDown(0)

        return res
    
    def _percDown(self, i):
        left = 2*i + 1
        right = 2*i + 2
        min = i
        if left < len(self.heap) and self.heap[left] < self.heap[min]:
            min = left
        if right < len(self.heap) and self.heap[right] < self.heap[min]:
            min = right
        if min != i:
            self._swap(i, min)
            self._percDown(min)
            

    def _swap(self, i, j):
        '''Swap the items at indices i and j in self.heap.'''
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
        
    def size(self):
        '''Return the number of elements in the heap.'''
        return len(self.heap)
    
    def findMin(self):
        '''Return the highest priority (smallest) item.'''
        return self.heap[0]