前言

堆排序需要将一颗完全二叉树构建成一个大顶堆或者小顶堆，然后将堆顶和最后的数字交交换

什么是大顶堆？

二叉树的性质四

• 具有n个节点的 完全二叉树 的深度为int(log_2n)+1 或者 math.ceil(log_2(n+1)) # log_2 对数的意思
• int(math.log(n)) + 1

二叉树的性质五
如果有一颗n个结点的完全二叉树（深度为性质4）.结点按照层序编号(i)，如下：

        1
        
    2       3
    
  4   5   6   7
  
 8 9  10

• 如果i=1，则结点i是二叉树的根，无双亲；
• 如果i>1，则其双亲是int(i/2)，向下取整。就是子节点的编号除以2得到的就是父结点的编号。
• 父结点如果是i，那么左孩子结点就是2i，右孩子结点就是2i+1
• 如果2i>n，则结点i无左孩子，即结点i为叶子结点；否则其左孩子结点存在编号为2i
• n>2i 说明存在右孩子, 且标号为： 2i+1
• 如果2i+1>n，则结点i无右孩子，注意这里并不能说明结点i没有左孩子；否者右孩子结点存在编号为2i+1
• 完全二叉树父亲结点一共有 n//2 个（包含根结点）

打印二叉树

构建大顶堆

        20
        
    40       50

构建单个二叉树

如上面的大顶堆，我们先判断改大顶堆是否有左孩子，然后判断右孩子
如果 有左孩子，我们假设左孩子是最大的那个树
然后判断是否有右孩子，如果有左孩子和右孩子比较，如果右孩子大于左孩子，保存右孩子为最大值
最后和父结点进行比较，如果大于父结点就交换位置，否则不变

代码实现

def max_heap(i, n, array):
    """
    调整数据为大顶堆
    :param i:   根节点的标号
    :param n:   结点个数
    :param array:   带构建的数据
    :return: list 构建好的大顶堆
    """
    while 2 * i <= n:
        # 性质五：如果2i>n，则结点i无左孩子
        # 这里表示有左孩子就进入循环
        l_index = 2 * i
        # 左孩子编号 2i
        max_index = l_index
        # 假设最大的就是左孩子，这里保存索引
        if 2 * i + 1 <= n and array[l_index] < array[2 * i + 1]:
            # 如果存在右孩子且右孩子大于左孩子，最大值索引为右孩子
            max_index = 2 * i + 1
        if array[max_index] > array[i]:
            # 最大值和根结点比较，如果最大值真的大于根节点，则交换位置
            array[max_index], array[i] = array[i], array[max_index]
            i = max_index
            # 修正i，继续向下调整直到不存在孩子结点
        else:
            # 没有孩子结点就退出循环
            break
    return array

全面调整二叉树为大顶堆

上面的算法从堆顶构建的话，不能达到我们的目的，但是从最后一个父结点开始就可以达到我们的目的
代码实现

def all_heap(total, array):
    """
    调整整个数据为大顶堆
    :param total: 结点个数
    :param array: 结点列表 
    :return: list
    """
    for i in range(total//2, 0, -1):
        # 父亲结点个数： 结点数 // 2
        max_heap(i, total, array)
        # 因为这里全是引用类型，没有拷贝数据。节省了内存空间
        # 从最后一个父结点开始调整
    return array

升序排序

将堆顶和最后一个交换，然后重新构建大顶堆

然后根系结点和最后一个结点进行交换

origin = [0, 30, 20, 80, 40, 50, 10, 60, 70, 90]
origin = all_heap(len(origin) - 1, origin)
# 构建大顶堆， 其实没有执行任何拷贝，直接调用函数就可以实现对origin的更改
def sort(total, array)：
    """
    排序
    :param total: 结点个数
    :param array: 结点列表
    :return: list
    """
    while total > 1:
        array[total], array[1] = array[1], array[total]
        total -= 1
        max_heap(1, total, array)
        # 重构大顶堆，因为不要最后一个结点参与，所以total - 1
        if total == 2 and array[total] >= array[total - 1]:
            # 如果 标号为2的结点 大于或等于根节点就不做调整了
            break
    return array

到此，排序完成