def adjust_heap(lst, i, size):
    lchild = 2 * i + 1      # 计算两个子节点的位置
    rchild = 2 * i + 2
    max = i
    if i < size // 2:
        if lchild < size and lst[lchild] > lst[max]:
            max = lchild
        if rchild < size and lst[rchild] > lst[max]:
            max = rchild

        # 如果max != i成立,那么就说明,子节点比父节点大,要交换位置
        if max != i:
            lst[max], lst[i] = lst[i], lst[max]
            # 向下继续调整,确保子树也符合堆的定义
            adjust_heap(lst, max, size)

def build_heap(lst):
    for i in range((len(lst)//2)-1, -1, -1):
        adjust_heap(lst, i, len(lst))
        print (lst)   # 此处输出,可以观察效果

lst = [3,9,2,6,1,4,8]
build_heap(lst)
print (lst)

[9, 6, 8, 3, 1, 4, 2]

def adjust_heap(lst, i, size):
    lchild = 2 * i + 1      # 计算两个子节点的位置
    rchild = 2 * i + 2
    max = i
    if i < size // 2:
        if lchild < size and lst[lchild] > lst[max]:
            max = lchild
        if rchild < size and lst[rchild] > lst[max]:
            max = rchild

        # 如果max != i成立,那么就说明,子节点比父节点大,要交换位置
        if max != i:
            lst[max], lst[i] = lst[i], lst[max]
            # 向下继续调整,确保子树也符合堆的定义
            adjust_heap(lst, max, size)

def build_heap(lst):
    for i in range((len(lst)//2)-1, -1, -1):
        adjust_heap(lst, i, len(lst))
        print (lst)   # 此处输出,可以观察效果


lst = [3,9,2,6,1,4,8]
def heap_sort(lst):
    size = len(lst)
    # 建立一个堆,此时lst[0]一定是最大值
    build_heap(lst)
    print ('*'*20)
    for i in range(size-1, -1, -1):
        # 将lst[0] 与lst[i] 交换,这样大的数值就按顺序排到了后面
        lst[0], lst[i] = lst[i], lst[0]
        # 交换后,重新将0到i这个范围内的数据调整成堆,这样lst[0]还是最大值
        adjust_heap(lst, 0, i)
        print (lst,i)  # 此处输出可以查看效果

heap_sort(lst)
print ('*'*20)
print (lst)