时间复杂度O(nlogn)
运行时间对比：快排<归并<堆排
极端情况下：
快排：极端下效率低
归并：需要额外的内存开销
堆排：在极端快的排序中相对较慢
堆是特殊的完全二叉树，有大顶堆（结点的值大于左右孩子）和小顶堆（结点的值小于左右孩子）
如有列表[7,6,3,4,1,2,5,9,0,8]
则二叉树为

                7
          6           3
    4        1      2    5
 9    0   8

先调整，使他从大到小有序排列，也就是最高结点下的两个堆里都按大小顺序排

                9
          8            5
     6        7     2    3
 4    0    1

这时候最大的数字就在最上面，然后开始把数字依次弹出排序，这里为了节省内存就将其放置在最后，将其与最后的数调换位置，也就是9和1换个位置，然后下次排序时就不算最后的数，因为9是最大且放置在最后了，依次重复操作
代码如下

def sift(list, low, hight):
    i = low #i就是指向父结点
    j = 2 * i + 1 #j是指向左孩子，左孩子与父亲的关系就是2i+1
    tmp = list[i] #这个是父结点的值
    while j <= hight: #hight是最后的数，也就是孩子还在这个堆里时
        if j < hight and list[j] < list[j+1]: #如果存在右孩子且右孩子比左孩子大则j指向右孩子
            j += 1
        if tmp < list[j]: #对比j指向的值是否大于父结点，如果大则进行以下操作
            list[i] = list[j] #j指向的孩子代替父结点的值
            i = j #i原来是指向父结点的，现在指向j结点也就是孩子结点
            j = 2 * i + 1 #这些调整结束，然后j指向孩子结点的左孩子，便于while的循环操作
        else:
            break 
    list[i] = tmp #这时候的i指向可能是孩子结点，所以将原来父结点的值放置于孩子结点里

def heap(list):
    n = len(list)
    for i in range(n // 2 - 1, -1, -1): #对二叉树进行排序，且n//2-1为最后一个数的父结点的位置，这个时候是从最后的父结点开始排
        sift(list, i, n-1) #排完序就是9在最上面，左右孩子的堆都排完序，这时候列表就是[9,8,5,6,7,2,3,4,0,1]
    for i in range(n -1,-1,-1): #对于已排完序的二叉树将最上面的数依次弹出，放置于最后
        list[0],list[i] = list[i],list[0] #最上面的数与最后的数交换，第一次就是9和1进行交换，
下次交换最后的数不是9，因为下次交换不把9列入二叉树里
        sift(list,0,i-1) #由于前面已经交换，所以交换完最上面的数可能不是二叉树内最大的数（9已不算，这时候只算9个数字），
应该重新选择最大的数放置上面，就这样依次进行

ab = [7,6,3,4,1,2,5,9,0,8]
heap(ab)
print(ab)