def heapify(nums, start, end):
    parent = start
    son = parent * 2 + 1
    while son <= end:
        if son + 1 <= end and nums[son] < nums[son + 1]:
            son += 1
        if nums[parent] > nums[son]:
            return
        else:
            nums[parent], nums[son] = nums[son], nums[parent]
            parent = son
            son = parent * 2 + 1


def heap_sort(nums):
    n = len(nums)
    for i in range(n // 2 - 1, -1, -1):
        heapify(nums, i, n - 1)
        print(nums)

    for i in range(n - 1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        heapify(nums, 0, i - 1)
        print(nums)


if __name__ == '__main__':
    # https://leetcode.cn/problems/sort-an-array/description/
    _nums = [7, 10, 13, 15, 4, 20, 19, 8]
    heap_sort(_nums)
    print(_nums)