排序、堆、优先队列：从比较器到手写堆的算法竞赛指南

打算法竞赛这几年我见过太多选手在排序、堆、优先队列这三样基础板子上翻车。很多人以为它们就是 std::sort 拍一下、priority_queue 声明一下的事可真到了赛场上自定义比较器写反、堆的手写模板漏掉边界、优先队列删不掉指定元素这类问题分分钟能把人卡住。这篇文章把我这几年的理解重新梳理了一遍排序的比较器到底要遵守哪些规则堆的向上向下调整为什么那么写STL 优先队列有哪些隐藏行为以及这三个知识点怎么组合成经典题型的套路。不管你是刚开始打比赛的新手还是想查漏补缺的老选手这篇都值得收藏。1. 为什么排序、堆、优先队列是竞赛里的隐藏深水区1.1 它们三个其实是同一套思想排序、堆、优先队列表面上是三个独立知识点本质上都和元素之间的序关系有关。排序是把一个序列整理成线性有序堆是在不断变化的数据集合里维护一个偏序结构优先队列则是每次取极值的抽象接口。你会发现堆排序就是堆 排序的合体优先队列的内部实现就是堆。理解了这个关系学起来就不会一片一片地背模板而是能串成一条线。很多同学问既然有 STL 的 sort 和 priority_queue为什么还要学堆原理答案是竞赛题不会永远只考 API。比如某些需要修改堆中某个元素的优先级的题目STL 的 priority_queue 就无能为力必须手写堆并维护元素位置数组。再比如卡常严重的题目priority_queue 的 vector 扩容和函数调用开销可能成为瓶颈手写定长数组堆反而更稳。所以我的建议是板子要会抄原理也要懂到能默写的地步。1.2 到什么程度才算会了我给个自检清单你对照一下就知道自己是不是真会了能解释 sort 和 stable_sort 的时间复杂度与稳定性差异能在 5 分钟内手写出正确的二叉堆 push 和 pop不查资料知道 priority_queue 的自定义比较器为什么直觉上是反的知道什么时候该用 multiset 冒充可删除的优先队列什么时候该手写堆。如果上面四条你都能答得明明白白这篇你主要看后面的题型组合和坑点就行如果还有含糊我建议从头跟一遍因为这些知识点在比赛里几乎是所有高级数据结构题的底层依赖。2. 排序不只是 sort()比较器、稳定性与离散化2.1 各排序算法的适用场景竞赛选手真正需要手写的排序其实不多绝大多数场景一个 std::sort 就够了。但我们得知道它的本质STL 的 sort 通常实现为内省排序是快排、堆排、插入排序的混合体平均和最坏都是 O(n log n)但是不稳定也就是说值相等的元素排序后相对顺序可能改变。什么时候需要用 stable_sort当题目要求按某个关键字排同时保留原本输入顺序时就得用比如按分数从高到低排同分按报名顺序保留。先看一张常用排序的对比表排序方式平均复杂度最坏复杂度是否稳定主要用途std::sortO(n log n)O(n log n)否通用排序std::stable_sortO(n log n)O(n log^2 n)是多关键字保序计数排序O(n V)O(n V)是值域小的整数基数排序O(d(n V))O(d(n V))是大整数/字符串堆排序O(n log n)O(n log n)否原地排序/手写板子表里 V 是值域大小d 是位数。stable_sort 在最坏情况下内存不足时退化为归并插入复杂度会高一些平时不用纠结这个细节记住要稳定就找它就行。离散化是排序最常见的应用之一。把一个大值域的数组压缩成 1 到 m 的排名步骤就是复制数组、排序、去重、然后 lower_bound 查找sort unique lower_bound 三件套。这样可以把值域从 1e9 压到 n后面建线段树、树状数组就方便了。这个套路会在很多题里反复出现建议当成条件反射来练。2.2 自定义比较器必须遵守的规则我在群答疑时看到最多的问题就是比较器写崩。C 的 sort 比较器必须满足严格弱序strict weak ordering三个核心要求反自反性cmp(a, a) 必须返回 false反对称性cmp(a, b) 和 cmp(b, a) 不能同时为 true传递性cmp(a, b) 和 cmp(b, c) 为 true 时cmp(a, c) 也必须为 true。最常见的错就是写成return a b;或return a b;。当两个值相等时 cmp(a, b) 和 cmp(b, a) 都返回 true违反反对称性sort 内部行为就变成未定义轻则结果错乱重则数组越界直接崩。正确写法要么return a b;升序要么return a b;降序。另外比较器里不要夹带读操作、随机数、或者会变的全局状态。你永远不知道 sort 内部会调用多少次比较顺序也完全不可预测一旦比较器带副作用结果基本没法复现排错的时候会非常痛苦。2.3 结构体多关键字排序的两种标准写法竞赛里结构体排序太常见了我给出两个都算标准的模板。第一种是重载小于号struct Student { int score; int id; bool operator (const Student other) const { if (score ! other.score) return score other.score; // 分数高在前 return id other.id; // 相同则 id 小在前 } }; // sort(v.begin(), v.end());第二种是传 lambda适合不想污染结构体定义的情况sort(v.begin(), v.end(), [](const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; return a.id b.id; });两种都行但注意多关键字优先级要写成逐层 if-else而不是一股脑用算术表达式拼接否则可读性很差调 bug 的时候也难看出规则对不对。排序看起来基础其实决定了后面很多题的调试成本值得一开始就写规整。3. 手写二叉堆把优先队列的八股文吃透3.1 二叉堆的存储与两个核心操作堆是一棵完全二叉树用小根堆举例任意节点的值小于等于它的两个孩子。最有用的实现方式是数组存树下标从 1 开始节点 i 的左右孩子分别是 2i 和 2i1父亲是 i/2。这样省掉指针缓存友好代码也短。维护堆的性质只有两个操作向上调整sift up和向下调整sift down。向上调整发生在 push 的时候。新元素先放数组末尾然后不断和父亲比较如果比父亲小就交换直到不再小于父亲或者到根const int MAXN 100000 5; int heap[MAXN]; int sz 0; void up(int p) { while (p 1 heap[p] heap[p 1]) { swap(heap[p], heap[p 1]); p 1; } } void push(int x) { heap[sz] x; up(sz); }向下调整发生在 pop 的时候。根被取走后把最后一个元素搬到根然后不断跟两个孩子里较小的那个比较如果比孩子大就交换void down(int p) { while ((p 1) sz) { int son p 1; // 左孩子 if ((son | 1) sz heap[son | 1] heap[son]) son | 1; // 右孩子更小换成右孩子 if (heap[p] heap[son]) break; swap(heap[p], heap[son]); p son; } } void pop() { heap[1] heap[sz--]; down(1); } int top() { return heap[1]; }两个操作都是沿着树高走复杂度 O(log n)。注意子树必须已经是合法堆up 和 down 才成立这也是为什么它们总是成对出现在标准流程里。这个先放到末尾再往上浮 / 先搬到根再往下沉的思路就是整个堆的全部秘密。3.2 为什么建堆可以做到 O(n)很多人默认建堆是 n 次 push复杂度 O(n log n)。但其实还有更优的建堆方式从最后一个非叶子节点开始从后往前调用 down。完全二叉树里最后一个非叶子节点是 n/2所以// 已知数组 a[1..n] 乱序 for (int i n / 2; i 1; --i) down(i);为什么这是 O(n)因为大部分节点都在靠近叶子的位置向下调整的路径很短。每一层节点数乘以该层最多向下走的步数累加出来是一个收敛于 O(n) 的量级。这个技巧在做堆排序和需要整体建堆的题目里很实用能省下不小常数。3.3 堆排序与 TopK 的经典套路堆排序就是先 O(n) 建堆然后重复取根、跟末尾交换并缩小范围。不过竞赛里很少单独考堆排序堆更常用的场景是 TopK从 n 个数里找最大的 k 个。思路是用一个大小为 k 的小根堆扫描所有数。如果堆没满就 push如果当前数比堆顶当前最小的候选大就 pop 掉堆顶再 push 当前数。扫描结束后堆里剩下的就是最大的 k 个复杂度 O(n log k)在 n 很大、k 很小时比全局排序快得多。类似的题还有第 k 小、两个数组各取一个求前 k 小和等等只要抓住堆顶永远是当前候选里最弱的一个这个直觉就不容易走偏。4. priority_queue 的实战姿势从默认大根堆到自定义优先级4.1 默认行为与底层机制STL 的 priority_queue 默认是大根堆top() 返回最大的元素底层默认用 vector 实现二叉堆。声明方式priority_queueint pq; // 大根堆 priority_queueint, vectorint, greaterint pqMin; // 小根堆注意 greater 这个比较器是从小到大的排序规则套在优先队列上反而让顶变成最小。很多新手在这里第一次感受到反直觉优先队列的比较器表示的是谁更该沉底而不是谁在顶上。理解这一点后面自定义优先级就不会晕了。4.2 自定义优先级的三种写法如果元素是自定义结构体有三种常见写法。第一种在结构体里重载小于号这样默认 priority_queue 就能用struct Task { int t; int w; }; struct Node { int cost; int id; bool operator (const Node other) const { return cost other.cost; // 这样写之后cost 小的反而更大 } }; priority_queueNode pq; // 实际上是按 cost 从小到大取这里很多人会问为什么 operator 里写的是因为 priority_queue 默认用 less 比较取的是最大的那个我们想让 cost 最小的先出队就要让 cost 小的在 less 的比较意义下更大所以 operator 里反而要写。第二种用仿函数显式传比较器语义更清楚struct Cmp { bool operator() (const Node a, const Node b) const { return a.cost b.cost; // 返回 true 表示 a 应该排在 b 后面 } }; priority_queueNode, vectorNode, Cmp pq;第三种lambda 配合 decltypeauto cmp [](const Node a, const Node b) { return a.cost b.cost; }; priority_queueNode, vectorNode, decltype(cmp) pq(cmp);我会优先推荐第二种因为结构清晰、还能临时写更复杂的比较逻辑。第三种在需要捕获外部变量时很有用比如某些搜索类题目要按剩余步数来安排队列lambda 就能把上下文带进去。4.3 pair 的隐藏用法与常见坑priority_queuepairint,int 默认先比 first 再比 second这在很多题里是现成的技巧只要把优先级键放 first就省得自定义结构体。比如单源最短路的堆优化队列里存 (dist, node)每次取 first 最小的即可。常见坑有两个。一个是 pop 之前忘记判断堆是否为空另一个是 priority_queue 不支持查找和删除任意元素。如果你需要删除堆里某个不在顶部的元素直接做不了。常规替代方案是用 multiset或者懒惰删除把要删的元素标记为无效等它浮到顶部时再真正弹出。懒惰删除在滑动窗口类的题目里非常常见后面详细说。5. 三大经典组合拳贪心合并、最短路优化、双堆维护5.1 贪心合并经典合并果子类问题有一类题是这样的有 n 堆果子每次可以合并任意两堆代价是两堆数量之和问把所有果子合成一堆的最小总代价。贪心策略是每次合并当前最小的两堆用小根堆实现简直是量身定做priority_queueint, vectorint, greaterint pq; for (int i 0; i n; i) pq.push(a[i]); long long ans 0; while (pq.size() 1) { int x pq.top(); pq.pop(); int y pq.top(); pq.pop(); ans x y; pq.push(x y); } printf(%lld\n, ans);为什么贪心是对的你可以把整个合并过程想成一棵二叉树每堆果子在树里的深度就是它参与合并的次数总代价等于所有果子数 × 深度之和。要让这个和最小数量少的果子就该放在更深的叶子位置也就是每次先把最小的合并掉。这个思想在很多变形题里还能用比如合并石子求最少体力、每次合并代价为两堆长度之和等换汤不换药。5.2 优先队列在单源最短路优化里的角色带非负权的单源最短路问题教科书里经常用一个优先队列来维护当前已知最短距离的候选节点每次从队里取出距离最小的未确定节点用它去松弛相邻节点如果有更短距离就更新并入队。队列里存的是 (dist, node) 的 pairdist 越小优先级越高用小根堆正好。这个优化把每次找最小值的 O(n) 操作降到了 O(log n)整体复杂度大约是 O((n m) log m)。优先队列在这里的角色本质上是动态维护最小值和堆排序、TopK 完全同一个内核。具体算法叫什么名字不重要重要的是你看到每步取最小、取完还要更新、更新完又插入这样的流程就能立刻联想到优先队列。能形成这个条件反射图论题的速度会有明显提升。5.3 双堆维护中位数与滑动窗口的懒惰删除有一类题要求动态维护一个集合的中位数每次插入一个数后输出当前中位数。经典做法是双堆一个小根堆存较大的那一半一个大根堆存较小的那一半同时保证两个堆的大小差不超过 1中位数就是两个堆顶之一。核心操作是插入后平衡两堆大小代码很短但每一步都要想清楚两个堆顶分别代表什么别把较大一半的最小值和较小一半的最大值搞混。滑动窗口里要随时知道窗口内最大值如果窗口大小固定可以用单调队列但如果窗口内还要随机删除和插入单调队列就不够了。这时可以维护一个大根堆并配合懒惰删除把窗口滑出的元素记一个过期标记取堆顶时如果发现堆顶已经过期就 pop 掉直到堆顶是有效元素。要做到快速判断过期可以用一个额外数组记录每个位置是否仍在窗口内或者给每个元素带一个 id 字段。这个技巧我几乎每周都能用上比手写平衡树省事太多。6. 我踩过的坑和调试建议6.1 比较器违规带来的诡异 bug我在一次练习赛里写过sort(v.begin(), v.end(), [](int a, int b){ return a b; });小数据全对一到 10^5 级别的随机数据就开始乱序甚至崩溃。当时排查到怀疑人生最后发现是比较器违反了严格弱序。从那以后我给自己立了规矩任何自定义比较器写完先检查两点——相等时返回 false正反两个方向不会同时 true另外用随机大数组配一个正确版本对拍至少跑 20 组再提交。对拍是我强烈推荐的调试习惯。排序、堆这类数据结构题错误往往不是逻辑整体崩溃而是边界条件下悄悄出错。写个暴力版本数据生成器造随机数两边输出对比几秒钟就能暴露问题比人眼看半天日志高效得多。6.2 手写堆的下标和边界手写堆最容易错的是下标如果我下标从 0 开始孩子就是 2i1 和 2i2父亲是 (i-1)/2容易绕晕。我的建议是统一从 1 开始省掉一堆 1/-1。还有一个隐藏问题down 循环里(p 1) sz这个条件如果节点没有右孩子直接拿左孩子比就行了别访问 heap[p 1 | 1] 越界。另外一定要把 sz 在 pop 时先减掉再去访问 heap[1]顺序反了就会用已经无效的旧值污染结果。以前我还吃过一次数组开小的亏MAXN 只开了 n 那么长但堆排序过程中 push 和 pop 交错临时元素数量可能超过 n。这类题我现在的习惯是 MAXN 直接开 n 5多留余量不到特殊情况不考虑省那点内存。6.3 STL 优先队列不适合的场景STL 的 priority_queue 好用但也有三个不适合的场景。第一是需要删除指定元素它做不到考虑 multiset 或懒惰删除。第二是需要修改元素优先级比如最短路算法里如果要求更新后把旧条目真正移出队列STL 做不到只能用懒惰删除让旧条目等到顶了再被忽略或者干脆手写堆加位置数组做 decrease-key。第三是极小的 n 或者需要频繁建堆的题目STL 的 vector 扩容和多次构造析构可能比手写数组堆慢虽然通常不至于卡常数但遇到 10^7 级别的操作就要警惕。手写堆做 decrease-key 的套路是开一个 pos 数组记录每个下标在堆里的位置更新值时先改值再 up/down 一次。这种做法代码比 STL 长但能处理一类专门考这种操作的题目平时我优先用 STL只有明确需要定位元素才上手写堆。6.4 输入输出和常数的最后建议竞赛场景下如果排序和堆涉及大量输入输出记得关掉 cin 和 cout 的同步缓冲否则 IO 就成了隐性超时点。其次能用 pair 就用 pair能用 int 就别用 long long需要时再改。最后一点模板要背熟但更要理解每一步在干什么。比赛时我是先默写手写堆的空白代码测试一遍再复制到正式代码里用的虽然看起来笨但能在关键题上避免低级失误。我现在的习惯是每个模板配一个最小可运行示例比如手写堆就配一个输入若干数、依次 push 和 pop 输出的小程序比赛前花十分钟跑一遍。代码只有自己动手跑过、改过才真正算数这也是我从看得懂题解到能稳定过题之间最重要的一步。