OI-wiki 堆（Heap）数据结构全解：二叉堆实现、可并堆选型与对顶堆实战-平芜编程栈

OI-wiki 堆（Heap）数据结构全解：二叉堆实现、可并堆选型与对顶堆实战

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

堆（Heap）是一类基于完全二叉树/树形结构的优先队列抽象，是 OI/ICPC 竞赛与工程开发中维护动态极值、解决第 k 大查询等问题的核心工具。本文以 OI-wiki 的堆总述文档为骨架，结合仓库内二叉堆详解及其参考实现，系统梳理堆的定义、核心操作、各类堆的复杂度选型、二叉堆的数组实现与线性建堆，并给出基于std::priority_queue的对顶堆完整实战代码。读完本文，你将掌握如何根据操作需求在二叉堆、左偏树、配对堆等结构中做选型，并能独立写出可运行的对顶堆程序解决动态中位数类问题。

堆的定义与基本性质

在 OI-wiki 中，堆被定义为一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于或小于等于其父亲的键值。根据不等号方向的不同，堆分为两类：

小根堆（最小堆）：每个节点的键值都大于等于其父亲节点的键值，因此树根保存的是全局最小值；
大根堆（最大堆）：每个节点的键值都小于等于其父亲节点的键值，因此树根保存的是全局最大值。

一个常见的事实是：STL 中的priority_queue其实就是一个大根堆（详见 STL 容器适配器文档）。在不加限定的语境下，OI 社区习惯上用「堆」特指二叉堆，这一点在后文的分类对比中会反复出现。

堆支持的核心操作

以小根堆为例，堆主要支持以下操作，这也是判断一种数据结构能否称为堆的基准能力集：

插入一个数（insert）；
查询最小值（find-min）；
删除最小值（delete-min）；
合并两个堆（merge）；
减小一个元素的值（decrease-key）。

一些功能更强大的堆（即可并堆，如左偏树、配对堆、二项堆）还能高效地支持merge操作；还有一些堆支持可持久化，即可以对任意历史版本进行查询或操作，并产生新的版本。二叉堆虽然合并是 $O(n)$ 的，但因为其数组存储形态天然可持久化，在部分题目中依然有独特价值。

堆的分类与复杂度对照

不同堆结构在不同操作上的时间复杂度差异巨大，选型直接决定程序能否通过数据规模限制。OI-wiki 给出了下列完整对照表（原表数据来源于 Wikipedia 优先队列运行时间汇总）：

操作 \ 数据结构	配对堆	二叉堆	左偏树	二项堆	斐波那契堆
插入（insert）	$O(1)$	$O(\log n)$	$O(\log n)$	$O(\log n)$¹	$O(1)$
查询最小值（find-min）	$O(1)$	$O(1)$	$O(1)$	$O(1)$²³	$O(1)$
删除最小值（delete-min）	$O(\log n)$³	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$³
合并（merge）	$O(1)$	$O(n)$	$O(\log n)$	$O(\log n)$	$O(1)$
减小一个元素的值（decrease-key）	$o(\log n)$（下界 $\Omega(\log \log n)$，上界 $O(2^{2\sqrt{\log\log n}})$）³	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(1)$³
是否支持可持久化	$\times$	$\checkmark$	$\checkmark$	$\checkmark$	$\times$

从表中可以提炼出几条实用的选型经验：

只需要插入 + 查询/删除极值：二叉堆即可胜任，且可用 STL 直接实现，代码量最小；
需要高效合并两个堆：优先考虑左偏树、配对堆等可并堆。配对堆的merge均摊 $O(1)$、实现简单、常数小（仓库内配对堆文档有完整原理与代码）；
需要 decrease-key 且操作次数多：斐波那契堆理论最优，但常数大、实现复杂，竞赛中通常用配对堆作为替代；
需要可持久化：二叉堆（数组形态）、左偏树、二项堆支持，配对堆与斐波那契堆因依赖均摊势能分析而无法可持久化。

二叉堆：结构、数组存储与两个核心调整过程

二叉堆是堆家族中最常用、最容易手写实现的成员。OI-wiki 的二叉堆文档给出了完整推导，本节按结构、插入、删除、增加权值四个环节逐步展开。

结构：完全二叉树 + 堆性质

二叉堆是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（权值）。它同时满足：

结构性质：完全二叉树，即除最后一层外每一层都被填满，且最后一层的结点从左向右连续排列；
堆性质：父亲的权值不小于儿子的权值（大根堆）；对称地可以定义小根堆。

由堆性质可知，树根存储的必然是最大值，因此getmax（查询最大值）操作在 $O(1)$ 时间内即可完成。

由于是完全二叉树，二叉堆不需要显式存储指针，直接用数组/序列 $h$ 顺序存储即可：$h_i$ 的两个儿子分别是 $h_{2i}$ 和 $h_{2i+1}$，$1$ 号位置是根结点。这种紧凑的存储方式不仅省内存，还为可持久化（用线段树/可持久化数组代替普通数组）提供了便利。

插入操作与向上调整

插入操作要求插入一个元素后，堆依然是完全二叉树。最简单的方法是：插到最下一层最右边的叶子之后；如果最下一层已满，就新增一层。插入之后堆性质可能被破坏，此时执行向上调整：

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

可以证明，插入后只可能使该结点与祖先不满足堆性质，向上调整到根之后，其他结点都不会违反堆性质。向上调整的时间复杂度为 $O(\log n)$（最坏沿一条树链走到根）。

删除操作与向下调整

删除操作指删除堆中最大的元素，即删除根结点。若直接删根，树会分裂成两个堆，难以处理，所以通常采用插入操作的逆过程：把根结点与最后一个结点直接交换，然后删掉现在位于末尾的原根结点。此时新的根结点（原末尾结点）可能不满足堆性质，需要执行向下调整：

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

同样可以证明，删除并向下调整后，没有其他结点会不满足堆性质。时间复杂度为 $O(\log n)$。

增加某个点的权值

若要增加堆中某个点的权值，直接修改该点后，其权值只会超过父亲，因此向上调整一次即可恢复堆性质，时间复杂度 $O(\log n)$。注意这是大根堆语境下的操作；对于小根堆，对称地可以减小某个点的权值（即 decrease-key）。

二叉堆的参考实现

向上调整与向下调整是上述所有操作的核心，OI-wiki 给出了精炼的参考代码：

void up(int x) { while (x > 1 && h[x] > h[x / 2]) { std::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; std::swap(h[x], h[t]); x = t; } }

代码要点说明：

up(x)：循环中每次与父结点h[x / 2]比较，若当前结点更大则交换并上移；x > 1保证不越出根结点；
down(x)：先令t = x * 2（左儿子），若右儿子存在且更大则更新为右儿子（t++），若h[t] <= h[x]说明堆性质已恢复，提前break，否则交换并继续下移；x * 2 <= n保证存在儿子；
以上代码为大根堆版本；改为小根堆只需把两处比较符号反向（<换成>）。

基于这两个函数，插入、删除、修改权值可以组合实现：

// 插入元素 v h[++n] = v; up(n); // 删除最大值（根） std::swap(h[1], h[n]); n--; down(1);

建堆：$O(n \log n)$ 与 $O(n)$ 两种路线

从一个空堆开始插入 $n$ 个元素（不关心顺序），最朴素的做法是逐个push，总时间为 $O(n\log n)$。OI-wiki 给出了两种更优的批量建堆方法：

方法一：从根开始按 BFS 序做向上调整

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

这个做法本质上仍然是一个一个插入，只是元素被提前放进了数组，可以改善常数。最坏情况下时间复杂度的递推式为 $T(n) = T(n - 1) + \Theta(\log n)$，累加得 $T(n) = \Theta(n \log n)$。

方法二：从叶子开始逐个向下调整

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

换一种理解方式：每次操作都是在**「合并」两个已经调整好的堆**，这同时说明了正确性。由于叶结点无需调整，实际可以从序列约 $n/2$ 的位置开始循环，进一步改善常数。根据“每次合并两个堆”的递归结构，可写出递推式 $T(n) = 2T(n/2) + O(\log n)$，由主定理得 $T(n) = \Theta(n)$。

之所以能够 $\Theta(n)$ 建堆，本质原因是堆性质很弱，二叉堆并不唯一：只要满足“父不小于子”的偏序即可，而不像排序那样要求全局有序。这也是堆与排序类强约束结构之间的关键差异。

实战：STL`priority_queue`的堆语义

竞赛中最快的落地方式是利用 STL 的std::priority_queue，OI-wiki 在容器适配器文档中给出了完整用法。其本质就是一个二叉堆（默认大根堆），常用声明方式：

#include <queue> std::priority_queue<int> q1; // 大根堆（默认） std::priority_queue<int, std::vector<int>> q2; // 大根堆，显式底层容器 std::priority_queue<int, std::deque<int>, std::greater<int>> q3; // 小根堆

成员函数的时间复杂度与堆语义对应：

$O(1)$：top()访问堆顶、empty()判空、size()取大小；
$O(\log n)$：push(x)插入元素并调整、pop()删除堆顶元素。

自定义比较类型时需要注意：不可以跳过Container直接传入Compare；从 C++11 起若使用 lambda 定义比较器，必须将其作为构造函数参数传入，例如：

auto cmp = [](const std::pair<int, int> &l, const std::pair<int, int> &r) { return l.second < r.second; }; std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(cmp)> pq(cmp);

对顶堆：动态第 k 大与中位数的通用解法

“动态维护一个序列上的第 $k$ 大数，且 $k$ 值可能变化”是一类高频问题，OI-wiki 给出的推荐方案是对顶堆（dual heap），可以完全避免手写权值线段树或平衡树的繁琐。

对顶堆由一个大根堆与一个小根堆组成：

小根堆维护“大值”，即前 $k$ 大的数（包含第 $k$ 个）；
大根堆维护“小值”，即比第 $k$ 大数小的其他数。

两个堆整体构成的数据结构支持以下操作：

维护（rebalance）：当小根堆大小小于 $k$ 时，不断将大根堆堆顶元素取出插入小根堆，直到大小等于 $k$；当小根堆大小大于 $k$ 时，对称地反向搬运；
插入元素：若插入元素大于等于小根堆堆顶，则插入小根堆，否则插入大根堆，然后维护对顶堆；
查询第 $k$ 大：小根堆堆顶元素即为所求，$O(1)$；
删除第 $k$ 大：删除小根堆堆顶元素，然后维护对顶堆；
$k$ 值 $+1/-1$：根据新的 $k$ 值直接维护对顶堆。

复杂度分析：查询第 $k$ 大是 $O(1)$；由于每次插入、删除或调整 $k$ 值后，小根堆大小与期望的 $k$ 值最多相差 $1$，维护过程最多只移动一个元素，因此插入、删除、改 $k$ 均为 $O(\log n)$。

参考实现：SPOJ RMID2 - Running Median Again

以 SPOJ RMID2：

#include <iostream> #include <queue> using namespace std; int main() { cin.tie(nullptr)->sync_with_stdio(false); int t, x; cin >> t; while (t--) { // 大根堆，维护前一半元素（存小值） priority_queue<int, vector<int>, less<int>> a; // 小根堆，维护后一半元素（存大值） priority_queue<int, vector<int>, greater<int>> b; while (cin >> x, x) { // 若为查询并删除操作，输出并删除大根堆堆顶元素 // 因为这题要求输出中位数中较小者（偶数个数字会存在两个中位数候选） // 这个和上面的第k大讲解有稍许出入，但如果理解了上面的，这个稍微变通下便可理清 if (x == -1) { cout << a.top() << '\n'; a.pop(); } // 若为插入操作，根据大根堆堆顶的元素值，选择合适的堆进行插入 else { if (a.empty() || x <= a.top()) a.push(x); else b.push(x); } // 对对顶堆进行调整 if (a.size() > (a.size() + b.size() + 1) / 2) { b.push(a.top()); a.pop(); } else if (a.size() < (a.size() + b.size() + 1) / 2) { a.push(b.top()); b.pop(); } } } return 0; }

实现要点：

大根堆a存前一半（较小）元素，堆顶即“两个中位数候选中的较小者”；小根堆b存后一半（较大）元素。因此查询/删除中位数时直接操作a.top()即可，与“小根堆堆顶即第 $k$ 大”的通用讲述略有出入，但原理相同，属于同一技巧的变通；
每次插入后根据a.size()与总数的一半比较进行再平衡，保证两个堆的大小差不超过 1；
调整条件(a.size() + b.size() + 1) / 2中+1是为了让元素总数为偶数时大根堆稍大，从而能输出较小的中位数；
cin.tie(nullptr)->sync_with_stdio(false)用于加速 IO，避免大数据量下输入输出成为瓶颈。

该实现配套的评测数据位于 docs/ds/examples/binary-heap/：输入样例binary-heap_1.in首行1表示一组测试，随后以0结尾，-1表示“输出并删除中位数”；对应的标准答案binary-heap_1.ans为：

5 9 3 7

这一组数据可以直接用于本地验证上述代码的正确性。同类练习题还包括 SPOJ RMID - Running Median 与洛谷 P1801 黑匣子，后者是对顶堆配合离线排序处理“第 $i$ 次查询时求前 $k$ 个数中第 $j$ 小”的经典变式。

可并堆与更多堆结构

当题目明确要求 $O(\log n)$ 甚至 $O(1)$ 的堆合并时，二叉堆的 $O(n)$ 合并无法胜任，需要换用可并堆。OI-wiki 中与堆同级的文档包括：

左偏树：通过维护“dist”使合并沿较短链进行，merge、insert、delete-min 均为 $O(\log n)$，且支持可持久化，是可并堆中最常手写的一种；
配对堆：基于势能分析的均摊数据结构，merge 均摊 $O(1)$、decrease-key 均摊接近 $O(\log n)$，结构简单、常数小，但无法可持久化；
二项堆家族与斐波那契堆相关概念：见总述表的复杂度对比，斐波那契堆 decrease-key 均摊 $O(1)$，但实现复杂，实际竞赛中使用频率低。

选型建议总结：常规极值维护用 STLpriority_queue（二叉堆）；需要合并时首选配对堆或左偏树；需要可持久化时考虑二叉堆数组形态或左偏树的持久化版本。所有操作的复杂度依据均可回溯到上文完整对照表及其脚注（如二项堆连续插入的均摊 $O(1)$ 技巧、find-min 通过维护最小指针达到 $O(1)$ 等）。

单次插入的复杂度为 $O(\log n)$，但有 $k$ 次连续插入时，可创建一个只包含要插入元素的二项堆，再将此堆与原先的二项堆进行合并，均摊复杂度为 $O(1)$。
↩
可以保存一个指向最小元素的指针，在执行其他操作时修改该指针，即可在 $O(1)$ 的复杂度下进行查询。
↩
复杂度为均摊复杂度。
↩ ↩ ↩ ↩ ↩

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

OI-wiki 堆（Heap）数据结构全解：二叉堆实现、可并堆选型与对顶堆实战