def adjust_heap(res,start,end):

    '''

    调整大顶堆，其中res为待排序堆列表

    （为了便于操作res索引，res首位补0，真实数据索引从1开始）

    '''   

    i = start

    j = 2*i

    while j <= end:

        if j < end and res[j] < res[j+1]:

            j += 1

        if res[i] < res[j]:

            res[i],res[j] = res[j],res[i]

            i = j

            j = 2*i

        else:

            break

def swap(res,root,last):

    '''

    交换根节点与尾节点

    '''

    res[root],res[last] = res[last],res[root]

def sort_heap(res):

    '''

    堆排序

    '''

    res = [0] + res

    length = len(res) - 1

    last_par = length // 2  # 寻找父节点

    for i in range(last_par):

        adjust_heap(res,last_par - i,length)

    for i in range(length - 1):

        swap(res,1,length - i)

        adjust_heap(res,1,length - i - 1)

    return res[1:]

res = [50, 16, 30, 10, 60,  90,  2, 80, 70]

print(sort_heap(res))