# 堆排序

1. 第一步将无序集合构造成一个无序二叉堆
2. 从二叉堆的最后一个节(n/2)点开始,从子节点中找出最小的一个与父节点交换，
3. 将二叉堆的所有节点遍历一遍后即得到最小值，
4. 将最后一个叶子与该最小值交换，此时第一遍遍历完成
5. 重复2-4的步骤，直到排序完成

inputArr=[199383, 10, 34, -1, -32, -29, 4, 0, 34, 5, 4, 36, 1, 8, 123, 453, 1008]
print("未排序集合:{0}".format(inputArr))
length=len(inputArr)
sortArr=[None]*len(inputArr)

for sortIndex in range(0,length):
    # 剩余待排序的节点个数
    nodeIndex=(length-sortIndex)//2-1
    while nodeIndex>=0:
        node=[nodeIndex,nodeIndex*2+1,nodeIndex*2+2]
        min=inputArr[node[0]]
        for index in range(1,len(node)):
            max=inputArr[node[index]]
            if(min>max):
                inputArr[node[0]],inputArr[node[index]]=max,min
                min=max
        nodeIndex-=1
    # 第一轮排序的最小值
    sortArr[sortIndex]=inputArr[0]
    if(length-sortIndex-1==0):
        break
    # 将最后一个叶子与第一个节点交换
    inputArr[0]=inputArr[length-sortIndex-1]

print("已排序集合:{0}".format(sortArr))