class BinHeap:
    def __init__(self):
        self.heaplist = []
        self.heapsize = 0

    def left(self, i):
        return i * 2 + 1

    def right(self, i):
        return i * 2 + 2

    def heapify(self, i):
        l = self.left(i)
        r = self.right(i)
        # Знаки
        if l <= self.heapsize and self.heaplist[l] > self.heaplist[i]:
            largest = l
        else:
            largest = i
        # Знаки и последний индекс
        if r <= self.heapsize and self.heaplist[r] > self.heaplist[largest]:
            largest = r
        if largest != i:
            # Обмен значениями явный
            tmp = self.heaplist[i]
            self.heaplist[i] = self.heaplist[largest]
            self.heaplist[largest] = tmp
            self.heapify(largest)

    def buildHeap(self, list):
        self.heaplist = list
        # Из-за того, что у вас в процедуре используется <=, heapsize должен быть строго меньше, чтобы избежать выхода за пределы
        self.heapsize = len(list) - 1
        # Индексы также c середины и до нуля включительно
        for i in range(len(list) // 2, -1, -1):
            print(i)
            self.heapify(i)

    def heapSort(self):
        pass

    def extractMax(self):
        pass

    def getHeap(self):
        return self.heaplist

    def add(self, elem):
        self.heaplist[-1]= elem
        self.heapsize += 1
        i = len(self.heaplist) - 1
        while i > 1 and self.heaplist[i // 2] < elem:
            self.heaplist[i] = self.heaplist[i // 2]
            i //= 2
            self.heaplist[i] = elem
    def pop(self):
        if self.heapsize == 2:
            return self.pop()
        retval = self.heaplist[1]
        self.heaplist[1] = self.pop
        i = 1
        while 2 * i + 1 < self.heapsize \
        and self.heaplist[i] < max(self.heaplist[2 * i], self.heaplist[2 * i + 1]):

            if self.heaplist[2 * i] > self.heaplist[2 * i + 1]:
                self.heaplist[i], self.heaplist[2 * i] = self.heaplist[2 * i], self.heaplist[i]
                i = 2 * i
            else:
                self.heaplist[i], self.heaplist[2 * i + 1] = self.heaplist[2 * i + 1], self.heaplist[i]
                i = 2 * i + 1
        if 2 * i == self.heapsize - 1 and self.heaplist[i] < self.heaplist[2 * i]:
            self.heaplist[i], self.heaplist[2 * i] = self.heaplist[2 * i], self.heaplist[i]
        self.heapsize -= 1
        return retval



def print_heap(ar):
    ml = max(len(str(x)) for x in ar)
    ars = [('{:0'+str(ml)+'}').format(x) for x in ar]
    dp = len(bin(len(ar))) - 1
    print('*' * 2**(dp-2) * (ml + 1))
    for i in range(1, dp + 1):
        str_space = ' ' * max(0, 2**(dp-i-2) * (ml + 1) - 1 - ml // 2)
        sep_space = ' ' * max(0, 2**(dp-i-1) * (ml + 1) - ml)
        print(str_space + sep_space.join(ars[2**(i-1) - 1: 2**i - 1]))
    print('*' * 2**(dp-2) * (ml + 1))

# def pop(Heap):
#     retval = Heap[-1]
#     Heap[-1] = Heap.pop()
#     i = 1
#     while 2 * i + 1 < len(Heap) \
#           and Heap[i] < max(Heap[2 * i], Heap[2 * i + 1]):
#         if Heap[2 * i] > Heap[2 * i + 1]:
#             Heap[i], Heap[2 * i] = Heap[2 * i], Heap[i]
#             i = 2 * i
#         else:
#             Heap[i], Heap[2 * i + 1] = Heap[2 * i + 1], Heap[i]
#             i = 2 * i + 1
#     if 2 * i == len(Heap) - 1 and Heap[i] < Heap[2 * i]:
#         Heap[i], Heap[2 * i] = Heap[2 * i], Heap[i]
#     return retval

heap = BinHeap()
heap.buildHeap([ 9, 5, 6,2, 2, 1, 4, 12, 3, 30])
# heap.add(8)
# heap.add(150)
# heap.add(16)
# heap.add(72)
# heap.add(73)
# heap.add(74)
# heap.add(75)
# pop(heap.getHeap())
heap.pop()
print_heap(heap.getHeap())