【排序算法】堆排序

[leviosa-e]

https://oi-wiki.org/ds/binary-heap/

https://www.runoob.com/w3cnote/heap-sort.html

可视化过程：https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

又名 优先级队列/二叉堆。

结构

从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。

堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。

由堆性质，树根存的是最大值。

过程

核心步骤

可视化过程：https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

建议对照着可视化的堆排序过程先过一遍。

• 核心思想：

先在子树内按照大根堆的标准进行排序，再从下往上遍历，确保每一棵子树都满足大根堆的标准。

遍历完成，即排序完成。

• 堆排序由两个核心步骤组成：

1. 先在子树内按照大根堆的标准进行排序：
   1. 在一棵子树内，先比较两个叶子节点 h2i+1 和 h2i+2 的大小，得到较大的那个，比如下图中是 h2i+1。
   2. 再拿较大的 h2i+1 与 子树的树根 hi 进行比较，如果叶子节点较大，则交换位置。（也就是下边提到的向上调整）
   3. 这样就确保这棵子树内是符合大根堆的标准了。

2. 从右下角的子树开始，按从右往左，从下往上的顺序，对每一层的子树都进行第一步的大根堆标准化操作。如果遇到需要对换 树根 和 叶子结点 的，对换之后需要继续往下递归，确保对换后所有的子树依然是符合大根堆标准的。（这步向下递归也就是下边提到的向下调整）

执行完上述两步操作，就得到了一个大根堆，堆顶就是最大值。

如果要用堆排序对数组排序，那么得到了最大值后，需要将最大值从堆中删除（与右下角的叶子结点对换，然后删除，再重新进行向下调整，得到新的大根堆），继续计算出剩下的数组中的最大值，直到数组中只剩最后一个为止。这样才完成了完整的排序。

插入操作

插入操作是指向二叉堆中插入一个元素，要保证插入后也是一棵完全二叉树。

最简单的方法就是，最下一层最右边的叶子之后插入。

如果最下一层已满，就新增一层。

• 插入之后可能会不满足堆性质？

向上调整：

如果这个结点的权值大于它父亲的权值，就交换，重复此过程直到不满足或者到根。

可以证明，插入之后向上调整后，没有其他结点会不满足堆性质。

向上调整的时间复杂度是 O(log2n) 的。

• 如何理解这里的时间复杂度？

假设我们有 n 个元素，按照完全二叉树的排法，这棵树一共会有 log2n 层，每个元素向上调整最多都只会经历 log2n 次，所以单看向上调整的过程是 O(log2n)；

如果看总的排序的时间复杂度，应该是 O(nlog2n)。

删除操作

删除操作指删除堆中最大的元素，即删除根结点。

但是如果直接删除，则变成了两个堆，难以处理。

所以不妨考虑插入操作的逆过程，设法将根结点移到最后一个结点，然后直接删掉。

然而实际上不好做，我们通常采用的方法是，把根结点和最后一个结点直接交换。

于是直接删掉（在最后一个结点处的）根结点，但是新的根结点可能不满足堆性质……于是就需要向下调整。

• 向下调整：

在该结点的所有子节点中，找一个最大的，与该结点交换，重复此过程直到底层。

可以证明，删除并向下调整后，没有其他结点不满足堆性质。

时间复杂度 O(log2n)

增加某个点的权值

很显然，直接修改后，向上调整一次即可，时间复杂度为 O(log2n)

实现

我们发现，上面介绍的几种操作主要依赖于两个核心：向上调整和向下调整。

考虑使用一个序列 h 来表示堆。hi 的两个儿子分别是 h2i+1 和 h2i+2。h0 是根结点：