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)$1$O(1)$查询最小值find-min$O(1)$$O(1)$$O(1)$$O(1)$23$O(1)$删除最小值delete-min$O(\log n)$3$O(\log n)$$O(\log n)$$O(\log n)$$O(\log n)$3合并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}})$3$O(\log n)$$O(\log n)$$O(\log n)$$O(1)$3是否支持可持久化$\times$$\checkmark$$\checkmark$$\checkmark$$\times$从表中可以提炼出几条实用的选型经验只需要插入 查询/删除极值二叉堆即可胜任且可用 STL 直接实现代码量最小需要高效合并两个堆优先考虑左偏树、配对堆等可并堆。配对堆的merge均摊 $O(1)$、实现简单、常数小仓库内 配对堆文档 有完整原理与代码需要 decrease-key 且操作次数多斐波那契堆理论最优但常数大、实现复杂竞赛中通常用配对堆作为替代需要可持久化二叉堆数组形态、左偏树、二项堆支持配对堆与斐波那契堆因依赖均摊势能分析而无法可持久化。二叉堆结构、数组存储与两个核心调整过程二叉堆是堆家族中最常用、最容易手写实现的成员。OI-wiki 的 二叉堆文档 给出了完整推导本节按结构、插入、删除、增加权值四个环节逐步展开。结构完全二叉树 堆性质二叉堆是一棵二叉树并且是完全二叉树每个结点中存有一个元素权值。它同时满足结构性质完全二叉树即除最后一层外每一层都被填满且最后一层的结点从左向右连续排列堆性质父亲的权值不小于儿子的权值大根堆对称地可以定义小根堆。由堆性质可知树根存储的必然是最大值因此getmax查询最大值操作在 $O(1)$ 时间内即可完成。由于是完全二叉树二叉堆不需要显式存储指针直接用数组/序列 $h$ 顺序存储即可$h_i$ 的两个儿子分别是 $h_{2i}$ 和 $h_{2i1}$$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)$ 建堆本质原因是堆性质很弱二叉堆并不唯一只要满足“父不小于子”的偏序即可而不像排序那样要求全局有序。这也是堆与排序类强约束结构之间的关键差异。实战STLpriority_queue的堆语义竞赛中最快的落地方式是利用 STL 的std::priority_queueOI-wiki 在 容器适配器文档 中给出了完整用法。其本质就是一个二叉堆默认大根堆常用声明方式#include queue std::priority_queueint q1; // 大根堆默认 std::priority_queueint, std::vectorint q2; // 大根堆显式底层容器 std::priority_queueint, std::dequeint, std::greaterint q3; // 小根堆成员函数的时间复杂度与堆语义对应$O(1)$top()访问堆顶、empty()判空、size()取大小$O(\log n)$push(x)插入元素并调整、pop()删除堆顶元素。自定义比较类型时需要注意不可以跳过Container直接传入Compare从 C11 起若使用 lambda 定义比较器必须将其作为构造函数参数传入例如auto cmp [](const std::pairint, int l, const std::pairint, int r) { return l.second r.second; }; std::priority_queuestd::pairint, int, std::vectorstd::pairint, 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_queueint, vectorint, lessint a; // 小根堆维护后一半元素存大值 priority_queueint, vectorint, greaterint 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）数据结构全解：二叉堆实现、可并堆选型与对顶堆实战
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)$1$O(1)$查询最小值find-min$O(1)$$O(1)$$O(1)$$O(1)$23$O(1)$删除最小值delete-min$O(\log n)$3$O(\log n)$$O(\log n)$$O(\log n)$$O(\log n)$3合并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}})$3$O(\log n)$$O(\log n)$$O(\log n)$$O(1)$3是否支持可持久化$\times$$\checkmark$$\checkmark$$\checkmark$$\times$从表中可以提炼出几条实用的选型经验只需要插入 查询/删除极值二叉堆即可胜任且可用 STL 直接实现代码量最小需要高效合并两个堆优先考虑左偏树、配对堆等可并堆。配对堆的merge均摊 $O(1)$、实现简单、常数小仓库内 配对堆文档 有完整原理与代码需要 decrease-key 且操作次数多斐波那契堆理论最优但常数大、实现复杂竞赛中通常用配对堆作为替代需要可持久化二叉堆数组形态、左偏树、二项堆支持配对堆与斐波那契堆因依赖均摊势能分析而无法可持久化。二叉堆结构、数组存储与两个核心调整过程二叉堆是堆家族中最常用、最容易手写实现的成员。OI-wiki 的 二叉堆文档 给出了完整推导本节按结构、插入、删除、增加权值四个环节逐步展开。结构完全二叉树 堆性质二叉堆是一棵二叉树并且是完全二叉树每个结点中存有一个元素权值。它同时满足结构性质完全二叉树即除最后一层外每一层都被填满且最后一层的结点从左向右连续排列堆性质父亲的权值不小于儿子的权值大根堆对称地可以定义小根堆。由堆性质可知树根存储的必然是最大值因此getmax查询最大值操作在 $O(1)$ 时间内即可完成。由于是完全二叉树二叉堆不需要显式存储指针直接用数组/序列 $h$ 顺序存储即可$h_i$ 的两个儿子分别是 $h_{2i}$ 和 $h_{2i1}$$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)$ 建堆本质原因是堆性质很弱二叉堆并不唯一只要满足“父不小于子”的偏序即可而不像排序那样要求全局有序。这也是堆与排序类强约束结构之间的关键差异。实战STLpriority_queue的堆语义竞赛中最快的落地方式是利用 STL 的std::priority_queueOI-wiki 在 容器适配器文档 中给出了完整用法。其本质就是一个二叉堆默认大根堆常用声明方式#include queue std::priority_queueint q1; // 大根堆默认 std::priority_queueint, std::vectorint q2; // 大根堆显式底层容器 std::priority_queueint, std::dequeint, std::greaterint q3; // 小根堆成员函数的时间复杂度与堆语义对应$O(1)$top()访问堆顶、empty()判空、size()取大小$O(\log n)$push(x)插入元素并调整、pop()删除堆顶元素。自定义比较类型时需要注意不可以跳过Container直接传入Compare从 C11 起若使用 lambda 定义比较器必须将其作为构造函数参数传入例如auto cmp [](const std::pairint, int l, const std::pairint, int r) { return l.second r.second; }; std::priority_queuestd::pairint, int, std::vectorstd::pairint, 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_queueint, vectorint, lessint a; // 小根堆维护后一半元素存大值 priority_queueint, vectorint, greaterint 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），仅供参考
