#Author guo
'''
堆分为最大堆和最小堆
最大堆要求结点的元素都大于其孩子
最小堆要求结点元素都小于左右孩子
最大堆的根结点一定是这个堆中的最大值

堆排序就是把堆顶的最大数取出
剩余的堆继续调整为最大堆，以递归来实现
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  
从最后一个非叶子结点开始 对堆进行构造 从左到有，从下至上

'''

#步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
#将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。

def fixDown(a, k, n):  # 自顶向下堆化，从k开始堆化
    N = n - 1
    while 2 * k <= N:
        j = 2 * k
        if j < N and a[j] < a[j + 1]:  # 选出左右孩子节点中更大的那个
            j += 1
        if a[k] < a[j]:
            a[k], a[j] = a[j], a[k]
            k = j
        else:
            break


def heapSort(l):
    n = len(l) - 1
    for i in range(n // 2, 0, -1):
        fixDown(l, i, len(l))
    while n > 1:
        l[1], l[n] = l[n], l[1]
        fixDown(l, 1, n)
        n -= 1
    return l[1:]


l = [-1, 26, 5, 77, 1, 61, 11, 59, 15, 48, 19]  # 第一个元素不用，占位
res = heapSort(l)
print(res)