一、堆简介

堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。
每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。STL 中的priority_queue 其实就是一个大根堆。
（小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。
一些功能强大的堆（可并堆）还能（高效地）支持 merge 等操作。
一些功能更强大的堆还支持可持久化，也就是对任意历史版本进行查询或者操作，产生新的版本。

二、堆的分类

习惯上，不加限定提到“堆”时往往都指二叉堆。

三、二叉堆

结构

二叉堆是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。
堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。
由堆性质，树根存的是最大值（getmax 操作就解决了）。

插入操作

插入操作是指向二叉堆中插入一个元素，要保证插入后也是一棵完全二叉树。
最简单的方法就是，最下一层最右边的叶子之后插入。
如果最下一层已满，就新增一层。
插入之后可能会不满足堆性质？
向上调整：如果这个结点的权值大于它父亲的权值，就交换，重复此过程直到不满足或者到根。
可以证明，插入之后向上调整后，没有其他结点会不满足堆性质。
向上调整的时间复杂度是 O(log n) 的。
堆 - 图2

删除操作

删除操作指删除堆中最大的元素，即删除根结点。
但是如果直接删除，则变成了两个堆，难以处理。
所以不妨考虑插入操作的逆过程，设法将根结点移到最后一个结点，然后直接删掉。
然而实际上不好做，我们通常采用的方法是，把根结点和最后一个结点直接交换。
于是直接删掉（在最后一个结点处的）根结点，但是新的根结点可能不满足堆性质,需要向下调整。
向下调整：在该结点的儿子中，找一个最大的，与该结点交换，重复此过程直到底层。
可以证明，删除并向下调整后，没有其他结点不满足堆性质。
时间复杂度 O(log n)。

改变某个点的权值

很显然，直接修改后，向上调整/向下调整一次即可，通常我们会向上调整一次，然后再向下调整一次，时间复杂度为 O(log n)。

实现

我们发现，上面介绍的几种操作主要依赖于两个核心：向上调整和向下调整。
考虑使用一个序列堆 - 图3 来表示堆。堆 - 图4 的两个儿子分别是堆 - 图5 和堆 - 图6 ，是根结点：
堆 - 图7

void up(int x) {
  while (x > 1 && h[x] > h[x / 2]) {
    swap(h[x], h[x / 2]);
    x /= 2;
  }
}
void down(int x) {
  while (x * 2 <= n) {
    t = x * 2;
    if (t + 1 <= n && h[t + 1] > h[t]) t++;
    if (h[t] <= h[x]) break;
    swap(h[x], h[t]);
    x = t;
  }
}

建堆

考虑这么一个问题，从一个空的堆开始，插入 n 个元素，不在乎顺序。
直接一个一个插入需要 O(n log n) 的时间，有没有更好的方法？

方法一：使用 decreasekey（即，向上调整）

从根开始，按 BFS 序进行。

void build_heap_1() {
  for (i = 1; i <= n; i++) up(i);
}

方法二：使用向下调整

一种思路，从叶子开始，逐个向下调整

void build_heap_2() {
  for (i = n; i >= 1; i--) down(i);
}

换一种理解方法，每次「合并」两个已经调整好的堆，这说明了正确性。

应用

对顶堆

对于以下问题：

维护一个序列，支持两种操作：

向序列中插入一个元素
输出并删除当前序列的中位数（若序列长度为偶数，则输出较小的中位数）

这个问题可以被进一步抽象成：动态维护一个序列上第 k 大的数，k 值可能会发生变化。
对于此类问题，我们可以使用 对顶堆 这一技巧予以解决（可以避免写权值线段树或 BST 带来的繁琐）。
对顶堆由一个大根堆与一个小根堆组成，小根堆维护大值即前 k 大的值（包含第 k 个），大根堆维护小值即比第 k 大数小的其他数。
这两个堆构成的数据结构支持以下操作：

维护：当小根堆的大小小于 k 时，不断将大根堆堆顶元素取出并插入小根堆，直到小根堆的大小等于k ；当小根堆的大小大于 k 时，不断将小根堆堆顶元素取出并插入大根堆，直到小根堆的大小等于 k；
插入元素：若插入的元素大于等于小根堆堆顶元素，则将其插入小根堆，否则将其插入大根堆，然后维护对顶堆；
查询第 k 大元素：小根堆堆顶元素即为所求；
删除第 k 大元素：删除小根堆堆顶元素，然后维护对顶堆；
k 值变化：根据新的 k 值直接维护对顶堆。
典型例题：
中位数
https://www.luogu.com.cn/problem/P1168
对顶堆的使用
合并果子
https://www.luogu.com.cn/problem/P1090
贪心の典
荷马史诗
https://www.luogu.com.cn/problem/P2168
贪心の典*2

堆