堆的概念

堆：一种特殊完全二叉树，也就是二叉树必须全部是满的，但是最后一排可以从右向左缺失。

大根堆：每个节点都比他的子节点大

小根堆：每个节点都比子节点小

堆在代码中的形式

堆在代码中实际上就是列表，只不过我们根据堆与列表的关系，把列表中的数想象为了堆。

这个堆在列表中是这个样子的。

我们从上向下，从左到右依次写入列表中就是这个堆。

lsit=[1,5,4,3,2]

父节点跟左子节点的关系为i=2i+1

父节点跟右子节点的关系为i=2i+2

堆的向下调整

有时一个堆并不是大根堆的排序方式

或者这个堆左右子树是大根堆，但整体不是。

可以用这个向下调整的方式进行调整调整成为大根堆。

 堆排序的步骤

1.构建堆

2.取出最上面的数，然后把最后一行的最后一个数放到第一位

3.进行一次向下调整

4.再取出最上面的那个数

5.重复知道数字全部取出为止

构建堆

从最下面一行开始，选出最大的与他们上方的数字比较，把大数放到上面。

排好最底层之后，依次向上面进行向下调整操作。

向下调整代码

因为使用过程中会多次使用到向下调整的代码，所以尽量要提前写好函数。

def sort(li,up,dn):
    '''
    本函数用于堆的向下调整
    :param li:列表
    :param up: 堆顶的数
    :param dn: 列表最右边的数
    :return:
    '''
    i=up#定义父节点索引
    c=2*i+1#定义子节点索引
    top=li[i]#储存最上方的索引
    while c<=dn:#如果有子节点
        if c+1<=dn and li[c+1]>li[c]:#如果有右子节点而且比左节点大
            c=c+1#把子节点索引定义到右节点
        if li[c]>top:#如果子节点大于该节点
            li[i]=li[c]#把子节点放到上面
            i=c#继续向下看
            c=2*i+1
        else:#如果不比他大
            li[i]=top#直接放到这里
            break
    else:#如果没有子节点了
        li[i]=top#直接放下
    return li

构建堆代码

原理：找到最后一个不是叶子节点的节点，然后依次向前进行向下调整

def dui_sort(li):
    n=len(li)#获取长度
    for i in range((n-2)//2,-1,-1):#找到最后的非叶子节点，然后依次向前
        sort(li,i,n-1)#进行向下调整

 依次出数代码

原理：最上面的数是最大的，那么把最上面的数跟堆最后面的数换位置，之后再把堆的范围减少一进行一次向下调整，然后再重复以上内容。

def dui_sort(li):
    n=len(li)#获取长度
    for i in range((n-2)//2,-1,-1):#找到最后的非叶子节点，然后依次向前
        sort(li,i,n-1)#进行向下调整
    for i in range(n-1,-1,-1):#i是堆最后的元素
        li[0],li[n-1]=li[n-1],li[0]#互换位置
        sort(li,0,i-1)#向下调整