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

打算法竞赛这几年，我见过太多选手在排序、堆、优先队列这三样"基础板子"上翻车。很多人以为它们就是 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？当题目要求"按某个关键字排，同时保留原本输入顺序"时就得用，比如按分数从高到低排，同分按报名顺序保留。

先看一张常用排序的对比表：

表里 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 和 2i+1，父亲是 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_queue<int> pq; // 大根堆 priority_queue<int, vector<int>, greater<int>> 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_queue<Node> 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_queue<Node, vector<Node>, Cmp> pq;

第三种，lambda 配合 decltype：

auto cmp = [](const Node& a, const Node& b) { return a.cost > b.cost; }; priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);

我会优先推荐第二种，因为结构清晰、还能临时写更复杂的比较逻辑。第三种在需要捕获外部变量时很有用，比如某些搜索类题目要按"剩余步数"来安排队列，lambda 就能把上下文带进去。

4.3 pair 的隐藏用法与常见坑

priority_queue<pair<int,int>> 默认先比 first 再比 second，这在很多题里是现成的技巧：只要把优先级键放 first，就省得自定义结构体。比如单源最短路的堆优化，队列里存 (dist, node)，每次取 first 最小的即可。

常见坑有两个。一个是 pop 之前忘记判断堆是否为空，另一个是 priority_queue 不支持查找和删除任意元素。如果你需要"删除堆里某个不在顶部的元素"，直接做不了。常规替代方案是用 multiset，或者"懒惰删除"：把要删的元素标记为无效，等它浮到顶部时再真正弹出。懒惰删除在滑动窗口类的题目里非常常见，后面详细说。

5. 三大经典组合拳：贪心合并、最短路优化、双堆维护

5.1 贪心合并：经典"合并果子"类问题

有一类题是这样的：有 n 堆果子，每次可以合并任意两堆，代价是两堆数量之和，问把所有果子合成一堆的最小总代价。贪心策略是每次合并当前最小的两堆，用小根堆实现简直是量身定做：

priority_queue<int, vector<int>, greater<int>> 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) 的 pair，dist 越小优先级越高，用小根堆正好。

这个优化把"每次找最小值"的 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 开始，孩子就是 2i+1 和 2i+2，父亲是 (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 输出的小程序，比赛前花十分钟跑一遍。代码只有自己动手跑过、改过，才真正算数，这也是我从"看得懂题解"到"能稳定过题"之间最重要的一步。