堆
简单介绍：
堆是利用完全二叉树的结构来维护一组数据，然后进行相关操作，一般的操作进行一次的时间复杂度在 ~
之间。
完全二叉树：若设二叉树的深度为 h，除第 h 层外，其它各层 ( 1～ h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
如图所示为一棵完全二叉树：
堆分为两种类型：大根堆、小根堆
顾名思义，就是保证根节点是所有数据中最大/小。
堆的存储：一个一维数组，节点编号从 1 开始，左儿子的编号 2x 、右儿子的编号 2x + 1 。
up 操作：
模拟：在堆中分别加入：{8，5，2，10，3，7，1，4，6}。如图所示：
以**小根堆**为例：从上面的数据中可以看出，根节点 `1` 元素 `8` 绝对不是最小的。我们很容易发现它的一个儿子节点 `3` (元素 `2` )比它来的小，我们怎么将它放到最高点呢？很简单，可以直接交换！但是，我们又发现了，`3` 的一个儿子节点 `7` (元素 `1` )似乎更适合在根节点。这时候我们是无法直接和根节点交换的，那我们就需要一个操作来实现这个交换过程，那就是 `up` 操作。从下往上找比自己大的数，然后递归交换。
操作过程如下：
从当前结点开始，和它的父亲节点比较，若是比父亲节点来的小，就交换，然后将当前询问的节点下标更新为原父亲节点下标；否则退出。
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
swap(h[u], h[u / 2]);
u >>= 1;
}
}
down 操作
这一次 up 完毕之后呢，我们又发现了一个问题，貌似节点 3 (元素 8 )不太合适放在那，而它的子节点 7 (元素 2 )好像才应该在那个位置。此时应该让节点 3 下沉！那么问题来了：节点 3 应该往哪下沉呢？我们知道，小根堆是尽力要让小的元素在较上方的节点，而下沉与上浮一样要以交换来不断操作，所以我们应该让节点 7 与其交换。
由此我们可以得出 down 的算法了：
让当前结点的左右儿子(如果有的话)作比较，哪个比较小就和它交换，并更新询问节点的下标为被交换的儿子节点下标，否则退出。
模拟操作图示：
void down(int u)
{
int t = u; // t 表示三个点中的最小值
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; // 左儿子
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;//右儿子
if (u != t) // 如果当前的父亲不是最小的，就交换，并递归处理
{
swap(h[u], h[t]);
down(t);
}
}
其他操作
插入操作：
如何在插入的时候维护堆的性质呢？每次插入的时候我们都在最后一个位置cnt 插入，然后 up(cnt)
弹出操作：
输出栈顶元素，也就是输出最小值。输出栈顶元素，然后让最后一个元素和栈顶进行交换，然后让现在的根元素 down 就可以了。
初始化堆操作
//o(n)建堆
for (int i = n / 2; i; i --) down(i);
i 为什么从 n/2 开始 down？
首先要明确要进行 down 操作时必须满足左儿子和右儿子已经是个堆。
开始创建堆的时候，元素是随机插入的，所以不能从根节点开始 down ，而是要找到满足下面三个性质的结点：
左右儿子满足堆的性质。
下标最大（因为要往上遍历）
不是叶结点（叶节点一定满足堆的性质）
那这个点为什么是 n/2 ？
通俗的说：从 n/2 开始，还有一个角度可以理解，因为 n 是最大值，n/2 是 n 的父节点，因为 n 是最大，所以n/2 是最大的有子节点的父节点，所以从 n/2 往前遍历，就可以把整个数组遍历一遍。
Q：为什么不能从根节点开始沉啊，为什么满足三个性质才能沉呢 ？
A：因为读进来的数是随机的，你建堆的时候可能根节点小于他的左右儿子，而根的左右儿子大于他们的左右儿子，这样排出来的数组就不对了，所以只能自下而上沉。
手写堆
手写实现堆的几个操作：
- 插入一个数
- 求集合中的最小值
- 删除最小值
- 删除任意一个元素
- 修改任意一个元素
例题：
原题链接：AcWing 838. 堆排序
堆排序补充
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序， 它的最坏、最好、平均时间复杂度均为
， 它也是不稳定排序。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值， 这种情况称为大顶堆，注意:没有要求结点的左孩子的值和右孩子的值的大小关系。
每个结点的值都小于或等于其左右孩子结点的值， 这种情况称为小顶堆。
大顶堆举例说明：
- 小顶堆举例说明：
- 一般升序采用大顶堆， 降序采用小顶堆。
基本思想：
- 将待排序序列构造成一个大顶堆。
- 此时，整个序列的最大值就是堆顶的根节点。
- 将其与末尾元素进行交换， 此时末尾就为最大值。
- 然后将剩余
n - 1个元素重新构造成一个堆， 这样会得到n个元素的次小值。 如此反复执行， 便能得到一个有序序列了。 - 可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了。
图解：
数组 {4,6,8,5,9} 要求使用堆排序法，将数组升序排序(升序采用大顶堆，降序采用小顶堆)。
6.1 构造堆
- 将给定无序序列结构如下。
-
从最后一个非叶子结点开始，从右至左，从下至上进行调整。
调整规则：找到该节点和他的所有儿子。如果该节点中存的值是找到节点值中的最大值，则不进行调整。如果不是，就将该节点的值和最大值进行交换，然后递归的调整和该节点交换值得那个节点。如下图：最后一个非叶子结点开始（也就是下面的 `6` 结点），从左至右，从下至上进行调整。`6` 有两个儿子：`5` 和 `9`，这三个值中 `9` 最大。`6` 和 `9` 交换。
因为 `6` 和 `9` 交换了，递归处理现在保存 `6` 的那个节点，发现它没有儿子，停止递归。
找到第二个非叶节点 `4` ，由于`[4, 9, 8]`中 `9` 元素最大，`4` 和 `9` 交换。
因为 `4` 和 `9` 交换了，递归处理现在保存 `4` 的那个节点: 找到它的两个儿子：`5, 6`, 其中 `6` 最大，交换 `4` 和 `6`。
然后继续递归处理，发现现在保存 `4` 的节点没有儿子，停止。
此时，我们就将一个无序序列构造成了一个大顶堆。
6.2 排序
将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。如下图：
-
将堆顶元素
9和末尾元素4进行交换。image -
重新调整结构（规则如上），使其继续满足堆定义
image -
再将堆顶元素
8与末尾元素5进行交换，得到第二大元素8。image -
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序。
image
6.3 总结：
将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆。
将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端。
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
6.4 完整代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt; //cnt 表示heap中有多少元素。下标从 1 开始
void down(int u)
{
int t = u;
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
swap(h[u], h[t]);
down(t);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
cnt = n;
for (int i = n / 2; i; i -- ) down(i);
while (m -- )
{
printf("%d ", h[1]);
h[1] = h[cnt -- ];
down(1);
}
puts("");
return 0;
}
参考资料：
本文供自己复习数据结构所用
