heap = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]


def heap_sort(heap):
    
    heapSize = len(heap)

    def get_parent(index):
        return (index-1)//2

    def get_left_child(index):
        return 2*index + 1


    def get_right_child(index):
        return 2*index + 2

    def max_heapify(index):
        l = get_left_child(index)
        r = get_right_child(index)

        if l < heapSize and heap[l] > heap[index]:
            largest = l
        else:
            largest = index

        if r < heapSize and heap[r] > heap[largest]:
            largest = r

        if largest != index:
            heap[index], heap[largest] = heap[largest], heap[index]
            max_heapify(largest)

    def build_max_heap():
        heapSize = len(heap)
        for i in range(len(heap)//2, -1, -1):
            max_heapify(i)

    build_max_heap()
    j = 0
    for i in range(len(heap)-1, 0, -1):
        heap[0], heap[i] = heap[i], heap[0]
        heapSize -= 1
        j += 1
        max_heapify(0)

print(heap)
heap_sort(heap)
print(heap)