from typing import *

class heap:
    def __init__(self):
        pass

    def __heapify(self, arr: List[int], n: int, i:int):
        # arr是数组，n是堆的容量，i是需要shift down的元素
        largest = i
        l, r = 2 * i + 1, 2 * i + 2
        if l < n and arr[largest] < arr[l]:
            largest = l
        if r < n and arr[largest] < arr[r]:
            largest = r

        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            self.__heapify(arr, n, largest)

    def heapify(self, arr: List[int]):
        n = len(arr)
        for i in range(n-1, -1, -1):
            self.__heapify(arr, n, i)
        return arr

    def add(self, arr: List[int], x: int):
        arr.append(x)
        if len(arr) < 2:
            return

        cur = len(arr) - 1
        p = (cur - 1) // 2
        while p >= 0 and arr[p] < arr[cur]:
            arr[p], arr[cur] = arr[cur], arr[p]
            cur = p
            p = (cur - 1) // 2

    def pop(self, arr: List[int]):
        if len(arr) == 0:
            return None
        elif len(arr) < 2:
            return arr.pop()

        rtn = arr[0]
        arr[0] = arr[-1]
        arr.pop()
        self.__heapify(arr, len(arr), 0)
        return rtn


if __name__ == '__main__':
    arr = [12, 3, 19, 0, 1999, 90, -1]
    h = heap()
    h.heapify(arr)

    print(arr)
    while len(arr) > 0:
        print(h.pop(arr))

    for each in [12, 3, 19, 0, 19999]:
        h.add(arr, each)
    print(arr)


