import random
# 调整
def sift(lst, low, high):
    child = 2 * low + 1  # 左孩子
    tmp = lst[low]
    while child < high:  # 孩子在堆里
        # 如果有右孩子且比左孩子大（找到左右孩子中较大的那个）
        if child + 1 <= high and lst[child] < lst[child+1]:
            child += 1  # 孩子指向右孩子
        # 孩子比父节点大
        if lst[child] > tmp:
            lst[low] = lst[child]  # 孩子调整到父节点上
            low = child  # 孩子成为新的父节点点
            child = 2 * low + 1  # 新的孩子节点
        else:
            break
    lst[low] = tmp  # 根节点放到父亲位置
# 堆排序
def heap_sort(lst):
    n = len(lst)  # 列表总长度，也就是最后一个值
    for i in range(n//2 - 1, -1, -1):
        sift(lst, i, n-1)
    # i指向堆的最后
    for i in range(n-1, -1, -1):
        # 根节点取出，最后一个孩子上位
        lst[0], lst[i] = lst[i], lst[0]
        sift(lst, 0, i-1)  # 调整出新根节点
lst = list(range(10))
random.shuffle(lst)
heap_sort(lst)
print(lst)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]