class PriorityQueue:
    '''implements a priority queue. Only priority values are inserted/retrieved,
a useful implementation should associate an "info" value to each priority while inserting, and
retrieveng the pair "priority, info" with maximum priority'''
    def __init__(self):
        '''builds an empty heap'''
        self._dim = 3  # initial dimension of the heap
        self._heap = [None] * self._dim  # builds a list containing self._dim items, all set to None
        self._n = 1  # number of elements currently used in the heap (minus 1)
                     # element in position 0 is not used.
                     # _n is the first available position in _heap
        
    def is_empty(self):
        '''returns True if and only if the PriorityQueue contains no elements'''
        return self._n == 1
    
    def insert(self, val):
        '''inserts a new priority value in the heap'''
        if self._n == self._dim: # if necessary, the heap is doubled appending None elements
            self._heap.extend([None] * self._dim)
            self._dim *= 2
        self._heap[self._n] = val # new item is initially put at the end
        pos = self._n
        self._n += 1
        while pos > 1 and self._heap[pos//2] < val: # swap with the parent if needed
            self._heap[pos], self._heap[pos//2] = self._heap[pos//2], self._heap[pos]
            pos = pos // 2
                
    def get_max(self):
        '''returns the maximum priority in the heap, None if it is empty'''
        if self._n == 1:
            return None
        else:
            return self._heap[1]
        
    def pop_max(self):
        '''removes the maximum priority from the heap, and returns its value.
Returns None if teh heap is empty'''
        if self._n == 1:
            return None
        else:
            max_val = self._heap[1]
            self._heap[1] = self._heap[self._n - 1]
            self._n -= 1
            self._heapify(1) # solve the possible violation in position 1
            return max_val
     
    def _heapify(self, pos):
        '''checks whether element in position "pos" is not greater that both children,
and swaps with the largest children'''
        left_child = 2 * pos
        right_child = 2 * pos + 1
        largest = pos
        if left_child < self._n and self._heap[left_child] > self._heap[pos]:
            largest = left_child
        if right_child < self._n and self._heap[right_child] > max(self._heap[left_child], self._heap[pos]):
            largest = right_child
        if largest != pos:
            self._heap[pos], self._heap[largest] = self._heap[largest], self._heap[pos]
            self._heapify(largest)  # if a swap occurred, the parent's position is recurseively checked
                
    def __str__(self):
        return f'{self._n-1} elements: ' + str(self._heap)