前置知识：

注意：实现堆需要用到完全二叉树的知识，如果未学习，点击了我也没用，因为我还没写

什么是堆？

堆（heap），又叫二叉堆，是一种基于完全二叉树实现的数据结构，它可以实现在堆顶的元素是整个堆里面最大的元素（大根堆），也可以是最小的元素（小根堆），进而获取到整个仪器中的最值的一种数据结构。通过它，我们可以快速获取一组数据中的最值，它的时间复杂度只有O(logn),堆同时也支持删除操作，不过它只能删除堆顶。

图解示范

首先我们先看完全二叉树的节点序号如下，可以发现一个父节点和子节点序号的关系：
设父节点序号为x,那么左子节点的序号为2x，右子节点的序号为2x+1
我们同时也可以知道一个节点x的父节点序号为x/2,（右子节点也是，因为int类型除以2默认向下取整）
完全二叉树的节点编号与父子节点关系

首先给出一个堆（这里我们以大根堆为例）

1
2
int w[MAXN];
int tot; //当前堆中节点的个数

插入操作前的大根堆初始结构

对于插入操作
假如我们插入一个5，我们将其插到数组的最后，作为叶子节点。
将新元素 5 插入堆尾后的结构

如果此时插入的子节点大于其父节点的值，违背了大根堆的性质，那么我们需要堆二叉堆进行修复(modify)操作
即向上比较，如果其大于父节点的值，那么便交换两者的位置.
向上修复时比较新元素 5 与父节点 1

因为5 > 1 所以与其父节点进行位置交换，然后接着进行修复操作，继续向上比较大小
交换元素 5 与父节点 1 后的堆结构

5 > 4,继续与父节点进行位置交换，然后接着向上进行比较，发现小于它的父节点，所以停止修复
可见整个修复过程是相对二叉堆来讲自下而上的修复。
元素 5 继续上移并完成插入修复

接着我们来讲删除堆顶的操作，首先我们无法直接删除堆顶，否则二叉堆会分裂为两棵树，修复麻烦巨大。
所以我们寻找一种合适的做法：先把堆顶和堆尾（数组的最后一个数）交换位置
删除堆顶前交换堆顶元素 8 与堆尾元素 0

然后我们将交换过去的堆顶在队尾删除。
接着我们发现堆顶的元素是一个较小（甚至最小）的数，违背了大根堆的原则，我们又需要对二叉堆进行修复(repair)
相对于前者的插入修复，这里的删除修复是一种自上而下的修复。
首先比较两个子节点的大小，接着父节点与子节点中较大的一个进行大小的比较，如果小于其中较大的节点，对二者进行交换。
选择其中较大的子节点是为了确保如果进行交换，交换上去的子节点是一个更大的数，这样满足大根堆的性质。
此处$0 < max(5,7)$,进行修复（交换0和7），然后接着向下判断
移除堆尾元素 8 后等待向下修复的堆

$0 < max(6,3)$,进行修复（交换0和6）
向下修复时交换堆顶元素 0 与较大的子节点 7

每一步也都要对修复的过程进行判断，如果已经是叶子节点（2x > tot） 那么停止修复，这里满足的就是这种情况
如果出现父节点的值大于两个子节点的值，也停止修复。
元素 0 继续与子节点 6 交换位置

这样，我们就完成了删除堆顶操作的修复操作。
删除堆顶并完成向下修复后的大根堆

代码示范

访问堆顶，很简单，根节点（1）即为最大值

1
int top() { return w[1]; }

修复到的节点序号为 $x$。如果 $x$ 已经是根节点，或者它不大于父节点，即 x == 1 或 **w[x] <= w[x / 2]**，就停止修复。
否则，交换x与父节点的值，然后接着向上递归修复。

1
2
3
4
5
6
7
8
9
10
void modify(int x) {
    if (x == 1 || w[x] <= w[x / 2]) return;
    swap(w[x], w[x / 2]);
    modify(x / 2);
}

void push(int x) {
    w[++tot] = x; //将x加到底部
    modify(tot); //自底向上递归修复
}

接下来是删除堆顶操作，详解请看备注
讲一下三目运算符 condition? x : y condition为布尔型判断，为真返回x，为假返回y

1
2
3
4
5
6
7
8
9
10
11
12
13
void repair(int x) {
    int tar = x * 2;
    if (tar > tot) return; //x已经是叶子节点
    if (tar + 1 <= tot && w[tar + 1] > w[tar]) tar++;
    if (w[x] >= w[tar]) return;
    swap(w[x], w[tar]);
    repair(tar);
}

void pop() {
    swap(w[1], w[tot--]); //交换堆顶与堆尾然后删除堆尾
    repair(1); //从根节点开始自上向下修复
}

自此我们实现了堆的所有操作，如果想要判断是否为空和堆的节点个数，通过tot的值便可以实现，这里不再给出具体的代码。

接下来我们引入一个模板题

堆的模板题

https://www.luogu.com.cn/problem/P3378
这是一道小根堆的模板题，大家可以前往自测，这里不做讲解只给出代码示范

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

const int MAXN = 1000005;
int w[MAXN];
int cnt;

int top() { return w[1]; }

void modify(int x) {
    if (x == 1 || w[x] >= w[x / 2]) return;
    swap(w[x], w[x / 2]);
    modify(x / 2);
}

void push(int x) {
    w[++cnt] = x;
    modify(cnt);
}

void repair(int x) {
    int tar = x * 2;
    if (tar > cnt) return;
    if (tar + 1 <= cnt && w[tar + 1] < w[tar]) tar++;
    if (w[x] <= w[tar]) return;
    swap(w[x], w[tar]);
    repair(tar);
}

void pop() {
    if (!cnt) return;
    swap(w[1], w[cnt--]);
    repair(1);
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            push(x);
        }
        if (op == 2) cout << top() << '\n';
        if (op == 3) pop();
    }
    return 0;
}

堆排序

题目描述

将读入的 $N$ 个数从小到大排序后输出。

输入格式

第一行为一个正整数 $N$。

第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

样例输入

1
2
5
4 2 4 5 1

样例输出

1
1 2 4 4 5

这是一个通过堆排序实现快排（用小根堆）的模板题，原理就是不断弹出堆顶，来从小到大输出数据。
大家可以前往洛谷进行自测 点我跳转
对比上一道题，这道题的做法就是将一组数据不断插入堆顶，然后输出一个，pop一个，进行n次操作。
下面是伪代码示范

1
2
3
4
5
6
7
8
9
10
11
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    push(x);
}
for (int i = 1; i <= n; i++) {
    cout << top() << " \n"[i == n];
    pop();
}

接着我们给出最后一道例题

[NOIP2004 提高组] 合并果子

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $n-1$ 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$ ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 $3$ 种果子，数目依次为 $1$ ， $2$ ， $9$ 。可以先将 $1$ 、 $2$ 堆合并，新堆数目为 $3$ ，耗费体力为 $3$ 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$ ，耗费体力为 $12$ 。所以多多总共耗费体力 $=3+12=15$ 。可以证明 $15$ 为最小的体力耗费值。

输入格式

共两行。
第一行是一个整数 $n(1\leq n\leq 10000)$ ，表示果子的种类数。

第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个整数 $a_i(1\leq a_i\leq 20000)$ 是第 $i$ 种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 $2^{31}$ 。

样例输入

1
2
3
1 2 9

样例输出

1
15

通过题目描述我们不难看出，先合并的石子在后面会参与到后续的合并过程，这就导致它的重量会在后面反复被消耗，即先合并的果子后面其被搬运的次数越多，通过贪心策略我们不难得知，较小的体力消耗的次数越多我们最后体力消耗的总数越少，所以我们实现一个小根堆，每次连续取出两个小根堆堆顶的值，然后再将两个堆顶的和插入到堆中，直到堆为空。
接下来给出伪代码

1
2
3
4
5
6
while (tot > 1) { //tot为2时完成最后一次合并
    int x = top(); pop();
    int y = top(); pop();
    push(x + y);
    sum += x + y;
}

优先队列（priority_queue）

优先队列（priority_queue）是一种由STL操作的特殊的队列，它可以实现队列的功能，在此之上，实现队首是整个队列中的最大值（或最小值）
它的底层逻辑是堆，需要包含<queue>头文件或者万能头，但是它只能访问队首（也就是最值）。
接下里我们给出使用方法

1
2
3
4
5
priority_queue<int> q;                                  // 大根堆
priority_queue<int, vector<int>, greater<int>> q;       // 小根堆
q.top();                                                // 查询堆顶
q.pop();                                                // 弹出堆顶
q.push(x);                                              // 插入元素

这样我们再回去做合并果子，并用 STL 优先队列完成这道题目。
给出代码示范

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    priority_queue<i64, vector<i64>, greater<i64>> q;
    for (int i = 1; i <= n; i++) {
        i64 x;
        cin >> x;
        q.push(x);
    }
    i64 ans = 0;
    while (q.size() > 1) {
        i64 x = q.top(); q.pop();
        i64 y = q.top(); q.pop();
        ans += x + y;
        q.push(x + y);
    }
    cout << ans << '\n';
    return 0;
}

总结与常见问题

常见问题

  • 为什么堆只能直接删除堆顶？ 数组中的堆只保证父子节点之间满足大小关系，并没有维护完整的有序序列；堆顶是唯一能立刻确定的最值。
  • 向下修复时为什么要选择更小或更大的那个子节点？ 只有把更合适的子节点换到父节点位置，交换后才能继续满足堆的性质。
  • priority_queue 默认是什么堆？ 默认是大根堆；加入 greater 后才是小根堆。
  • 合并果子为什么每次取最小的两堆？ 越早合并的重量会被重复计算越多次，因此应让较小的重量承担更多次计算。

复杂度分析

  • 访问堆顶：时间复杂度 $O(1)$。
  • 插入或删除堆顶：时间复杂度 $O(\log n)$。
  • 建堆：逐个插入为 $O(n\log n)$，自底向上建堆可做到 $O(n)$。
  • 堆排序与合并果子：时间复杂度 $O(n\log n)$，手写数组堆的空间复杂度 $O(n)$。

系列文章

  1. 队列（queue）
  2. 栈（stack）
  3. 堆（heap）
  4. 并查集
  5. 树状数组
  6. 离散化和lower_bound
  7. 前缀和与差分
  8. 二分
  9. 三分与单峰函数
  10. 交互题入门与常见模型