手把手拆解三大复杂排序算法（堆排序）
手把手拆解三大复杂排序算法（堆排序）
堆排序是一种基于树的排序算法，它利用最大堆或最小堆的性质，通过构建堆、不断调整堆来实现排序。它的优点是时间复杂度稳定在 O(nlogn)，空间复杂度低。缺点是实现稍微复杂一点，而且不如快速排序常用。不过，在一些对空间要求严格且需要稳定时间复杂度的场景下，堆排序是一个不错的选择。
一、算法介绍
排序算法是编程世界里最基础又最迷人的主题之一。今天，我们要深入探讨一种非常高效的排序算法——堆排序。
它不像冒泡排序那样简单直接，也不像快速排序那样以 partition 操作为核心，而是基于一种名为“堆”的数据结构。听起来有点复杂？别担心，我会从最基础的概念开始，一步步带你走进堆排序的世界。
二、基础概念：树与堆
（一）树是什么？
在理解堆之前，咱们得先搞懂树。树是一种数据结构，它由节点组成，就像家谱图一样，有父节点和子节点。最上面的节点叫根节点，下面的节点一层层分开，像一棵倒过来的树。
二叉树：就像家谱图，每个节点（可以理解为一个数据点）最多有两个 “孩子”，这两个孩子称为左子节点和右子节点。每层的节点数可能会不同，但它们都有一个共同点：每个节点最多有两个子节点。就像这样
满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。简单来说，就是我们从上到下，从左到右来绘制一个二叉树，如下图
（二）堆
堆是一种特殊的完全二叉树，分为两类：
- 大顶堆：父节点值 ≥ 子节点值（根节点为最大值）。
- 小顶堆：父节点值 ≤ 子节点值（根节点为最小值）。
就像前面的例子，父节点值均大于子节点值，故为大根堆（也可以叫大顶堆，最大堆等等），接下来我们将以大根堆为例，来介绍堆排序。
（三）父子节点的关系
那么，我们先来研究一下，父节点和左右孩子节点之间有什么关系？
首先看左孩子节点：
父节点下标 0 ，对应左孩子下标 1
父节点下标 1 ，对应左孩子下标 3
父节点下标 2 ，对应左孩子下标 5
父节点下标 3 ，对应左孩子下标 7
不难发现规律，如果父节点下标为 i ，那么左孩子节点下标就为 2i + 1
而右孩子节点是左孩子节点下标加一，也就是说对应左孩子节点下标就为 2i + 2
三、算法原理及实现
（一）向下调整函数
这是堆的核心操作，是构建和维护堆的关键操作，假设我们打乱了堆的结构，向下调整能把它 “修复” 好。
那么什么样的堆才可以修复？这里就是假设根节点的左右子树都是堆，但根节点不满足堆的性质，比如说下面这个例子，这里根节点应该要比 6 和 8 大，才满足整个大根堆的条件
那么这种情况下，我们就可以通过一次向下调整将其变成一个堆 ，如何调整，看下面示意图
（1）把根节点 3 拿出来，看看左右子节点谁更大，谁就能上去原来 3 的位置
（2） 8 比 6 大，8 到根节点位置，那么 3 能直接替换到原来 8 的位置吗？很明显，如果替换上去，那它的孩子节点 7 肯定就不满足了
（3）所以我们把 7 替换到第二层，然后看 3 能不能替换原来 7 的位置，因为已经没有孩子节点了，所以 3 就是在这个位置了
这样一来，就完成了一轮向下调整，那么接下来我们先实现一下这个函数
def shift(li,low,high):
#向下调整函数
i=low
j=2*i+1
tmp=li[low]
while j <=high:
if j+1<=high and li[j+1]>li[j]:
j=j+1
if li[j]>tmp:
li[i]=li[j]
i=j
j=2*i+1
else:
break
li[i]=tmp
在这个函数中，li 是待排序的数组，low 是根节点下标，high 是最后一个孩子节点下标，对应的 i 最开始是当前根节点下标， j 是 i 对应的左孩子下标，tmp 临时保存根节点的值；
为什么这里有这么多个变量，因为我们后续的操作可能是针对一棵子树，不一定是完整的树，
对应的进入 while 循环，我们是一层一层向下调整，所以条件是靠最后一个叶子节点下标来限制的，j <= high 就保证了叶子节点下标不会超过数组范围
if 语句解释：
第一个 if 条件，确保了当前节点对应右子节点存在，且右子节点的值比较大，那么我们就是把右子节点的值替换给父节点
if j+1<=high and li[j+1]>li[j]:
j=j+1
if li[j]>tmp:
li[i]=li[j]
i=j
j=2*i+1
else:
break
而第二个 if 则表示当前选中的孩子节点值，大于父节点值，那么就把父节点值更新，替换原来孩子为新的父节点，继续向下一层判断
最后，如果到了最底下，孩子节点比原来根节点大（就是前面的例子），那么第二个 if 条件满足，执行一次移动；若不满足，就是说明子节点比原根节点大，那么不用交换，直接结束循环，最后再把当前 i 所在位置的值替换为tmp。结合前面案例会更好理解。
（二）堆排序实现
有了向下调整函数，该如何实现堆排序？
主要分两步：
第一步，建立堆
第二步，一步一步取出堆顶元素（比如大根堆，我们取出堆顶就是最大值），不断向下调整
首先我们将数组元素从上到下，从左到右填入二叉树，得到一个完全二叉树，如下图
接下来，我们只需要从最后一个非叶子节点开始，向前依次执行向下调整函数即可
接下来，我们就是要把堆顶的值取出来，但是取出来放哪里？很显然放在一个新数组是不划算的，因为如果数组很大，那么会占用很多的额外空间，所以我们是将根节点和最后一个叶子节点交换位置，同时，将树的最后一个下标 -1 即可，也就是把下图左边的树看成右边的树，然后执行向下调整，如此往复，即可完成排序
那么堆排序代码如下
def heap_sort(li):
n=len(li)
#建堆
for i in range((n-2)//2,-1,-1):
shift(li,i,n-1)#i表示建堆时的根下标
#建堆完成
for i in range(n-1,-1,-1):
li[0],li[i]=li[i],li[0]
shift(li,0,i-1)#i-1是新high
这里解释一下 for 循环的条件，我们知道，前面的案例我们需要以下标 0 到 3 的节点，看成根节点，从下往上依次执行向下调整，那从哪开始？我们知道父节点 i 对应的两个子节点分别是 j = 2i+1 和 j = 2i + 2 ，那么 i 就可以等于 ( j - 1)整除2 ，而我们这里 n 是数组长度，所以就是从( n - 2)整除2开始，直到下标为0，而叶子节点其实不会有什么影响，比如我们下图叶子节点如果是判断 8 对应的子节点，那么它也是超过 n-1 了，所以这里条件直接用 n-1就可以
而第二个 for 循环也不难理解，就是从最后一个下标到第一个下标，执行 n 次调整交换
四、时空复杂度分析
- 时间复杂度：构建堆的时间复杂度是 O(n)。每次向下调整的时间复杂度是 O(logn)，因为堆的高度是 logn。排序过程中，需要进行 n - 1 次向下调整操作。所以，总的时间复杂度是O(nlogn)。
- 空间复杂度：堆排序是就地排序，不需要额外的存储空间，除了递归调用时的栈空间。最坏情况下，栈深度是 O(logn)。但一般来说，我们会说堆排序的空间复杂度是 O(1)，因为主要的操作都是在原数组上进行的。
五、总结
堆排序是一种基于树的排序算法，它利用最大堆或最小堆的性质，通过构建堆、不断调整堆来实现排序。它的优点是时间复杂度稳定在 O(nlogn)，空间复杂度低。缺点是实现稍微复杂一点，而且不如快速排序常用。不过，在一些对空间要求严格且需要稳定时间复杂度的场景下，堆排序是一个不错的选择。