C++堆实战：从priority_queue到手写堆的完整指南

1. 先把“堆”这件事说清楚：它到底能帮你解决什么问题

1.1 堆不是容器，而是一种“优先级的秩序”

很多 C++ 开发者刚接触堆的时候，习惯把它当成一种 STL 容器，就像 vector、map 那样去理解。但实际上，堆并不是一个具体的容器，它描述的是一种数据组织方式：在一个数组或者别的连续存储结构上，通过特定的位置关系，让最大（或最小）元素始终处于最前面。这个关系通常用完全二叉树来理解，父节点总是大于（或小于）它的子节点，于是整棵树从上到下就保持了一种“优先级的秩序”。

基于这个秩序，堆能提供两个极其关键的操作，而且都是 O(log n) 的复杂度：把新元素塞进堆里，以及把当前的最大（或最小）元素取出来。注意，不是取出任意元素，而是每次都取“优先级最高”的那个。这就让堆成为处理“动态数据中随时需要知道极值”这类问题的主力工具。

我在实际项目里接触它的第一个场景，是做一个实时日志分析模块。系统会不断产生日志事件，每个事件带有时间戳和严重级别，我需要随时知道当前最严重的那条日志是什么。如果每次都用 sort 或者直接线性扫描，日志量一上来就崩了；用堆之后，无论来多少条，取极值永远是 O(1)，代价只是每次插入或删除时的 log n 调整。这就是堆最核心的定位：它不为“有序遍历”服务，而是为“动态调度优先级”服务。

1.2 四个高频场景，让我决定在项目里引入堆

堆在 C++ 实战里最常见的四个场景，基本覆盖了 80% 的使用需求。第一个是 Top K 问题，比如从海量数据里找出最大的 100 个元素，用一个大小为 100 的最小堆就能在 O(n log K) 时间内搞定，内存占用和 K 有关，和数据总量无关。第二个是任务调度，进程调度、定时器管理、请求优先级队列，本质上都是“总是处理优先级最高的那个任务”，堆是教科书级别的实现方案。

第三个是求中位数或者百分位数，用“一个大顶堆 + 一个小顶堆”的组合可以做到 O(log n) 插入、O(1) 查询中位数，我第一次看到这个做法的时候觉得非常惊艳，后来在监控系统的耗时统计里直接用上了。第四个是合并多个有序序列，比如归并多个有序文件或者多个网络流，用堆维护每个序列的当前最小值，每次弹出一个再补一个，复杂度从 O(nk) 直接降到 O(n log k)。

这几个场景里，前两个用得最频繁，也是我下面要重点演示的。一句话总结我的经验：当你发现自己在“反复排序、只取极值、数据还在不断变更”的场景里写 for 循环找最大最小，就应该条件反射地想到堆。

2. 直接调用库函数：priority_queue 与四大堆算法

2.1 std::priority_queue：最省心的优先队列

C++ 标准库提供的 priority_queue，是大多数人进入堆世界的第一站。它包裹在 vector 之上，默认是一个最大堆，也就是 top() 返回的是当前容器里最大的元素。先看最基础的使用方式：

#include <queue> #include <vector> #include <iostream> int main() { std::priority_queue<int> pq; pq.push(10); pq.push(5); pq.push(20); pq.push(3); while (!pq.empty()) { std::cout << pq.top() << " "; // 输出：20 10 5 3 pq.pop(); } return 0; }

这段代码基本是“开箱即用”，不需要关心堆的具体结构。push 会自动把元素放到正确的位置，pop 会把最大元素移除并调整剩余元素。它的内部实现其实就是调用 std::push_heap 和 std::pop_heap，只是封装成了容器适配器的形态，对外屏蔽了底层细节。

不过 priority_queue 有几个受限点，初学阶段容易踩：它不提供迭代器，没法直接遍历；它没有清空操作 clear，只能重新赋值；它也不支持删除堆中任意元素。这些限制在我早期做日志模块时就踩过：需要把某条特定日志移除，结果发现 priority_queue 根本不提供 remove。后来我才意识到，priority_queue 的设计定位就是“只管往进放和往外弹极值”，如果需要删除中间元素，就得换用底层堆算法或者手写堆。

2.2 std::make_heap / push_heap / pop_heap / sort_heap：更底层的堆算法

priority_queue 方便，但不够灵活。标准库在 里其实还提供了一整套堆算法，可以直接作用在 vector、array 或者任意随机访问迭代器上。这四种算法我放在一起说，因为它们本身就是一个完整流程：

• make_heap：把一段随机访问区间调整成堆
• push_heap：把区间末尾的新元素插入到已有堆中
• pop_heap：把堆顶元素移到区间末尾，并调整剩余部分为堆
• sort_heap：对堆不断执行 pop，使整个区间变成升序

一个典型用法是维护一个动态数组堆：

#include <algorithm> #include <vector> std::vector<int> v = {9, 3, 7, 1, 8}; std::make_heap(v.begin(), v.end()); // 调整为堆 v.push_back(11); // 先放到末尾 std::push_heap(v.begin(), v.end()); // 再“上浮”恢复堆性质 std::pop_heap(v.begin(), v.end()); // 堆顶换到末尾 int max_val = v.back(); // 取出最大值 v.pop_back(); // 移除末尾元素

这种方式的灵活性就在于：底层数据仍然是 vector，你可以随时用下标访问，可以按需删除中间元素（尽管删除后需要重新调整堆），甚至可以在堆和非堆状态之间自由切换。sort_heap 的另一个巧妙用法，是把堆排序和 std::make_heap 直接组合，几乎等价于自己手写了一遍堆排序。

注意：push_heap 的前提是 [begin, end-1) 已经是堆，要插入的元素必须先 push_back 到末尾。如果忘记 make_heap 就直接 push_heap，行为是未定义的，这个坑我见过不少同事踩过。

2.3 自定义比较器：让“最大堆”翻车的那次实践

priority_queue 默认是最大堆，这其实是 C++ 和很多其他语言不一样的地方。Java 里 PriorityQueue 默认是最小堆，我第一次从 Java 转过来写 C++ 时，默认按最小堆的思路写代码，结果取出 top 值完全不是预期的顺序，调试了半天才发现比较器方向反了。

如果你想用 C++ 的 priority_queue 实现最小堆，有两种常见的写法：

#include <queue> #include <vector> #include <functional> // 方法一：用 greater std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq; // 方法二：自定义比较器，此时 p(a,b) 返回 true 表示 a 优先级低于 b auto cmp = [](int a, int b) { return a > b; }; std::priority_queue<int, std::vector<int>, decltype(cmp)> custom_pq(cmp);

方法二其实是更通用的方式，因为当你的元素是自定义结构体时，必须通过这个比较器来告诉堆“按什么规则排序”。这里有一个非常反直觉的细节：比较器返回 true 时，表示第一个元素的优先级低于第二个元素，因此会被放在堆的更低处。换句话说，如果你写 return a > b，那么较小的值有更高的优先级，形成最小堆。这个方向我对过很多次，建议每次写自定义比较器前，先在脑内模拟一遍：比较器里的 true 到底意味着谁“更弱”。

自定义类型的一个标准例子，是按任务优先级和时间戳排序的任务队列：

struct Task { int priority; int timestamp; }; struct TaskCompare { bool operator()(const Task& a, const Task& b) const { if (a.priority != b.priority) return a.priority < b.priority; // 优先级高的先出 return a.timestamp > b.timestamp; // 同样优先级，先来的先出 } }; std::priority_queue<Task, std::vector<Task>, TaskCompare> task_queue;

在这个例子里，比较器返回 true 意味着 a 的优先级“不如” b，所以在堆里 a 会“下沉”，优先级更高的 b 才能浮到堆顶。这种写法在定时任务、订单撮合、模拟仿真等模块里非常常见。

3. 手工实现一个最小堆：从 push 到 heapify 的完整拆解

3.1 为什么还要手写？真实场景里的三个理由

很多学 C++ 的人会问：标准库明明有 priority_queue，为什么还要自己写堆？我在工作里确实遇到过三个必须手写堆的场景，每个都很现实。

第一个场景是需要删任意节点。标准库的 priority_queue 不支持删除除堆顶以外的元素，而某些算法（比如 Dijkstra 最短路径的堆优化版本）在节点距离更新后，需要快速修改堆中某个节点的值，或者干脆删除一个指定节点。这时候必须手写一个带索引映射的堆，否则就得用“懒删除”方案，堆里堆大量的过期元素，内存和复杂度都受不了。

第二个场景是追求极致的性能和内存控制。标准库的 priority_queue 底层是 vector，动态扩容会拷贝元素，对于大型结构体来说代价非常高。手写堆时可以在栈上预分配固定大小数组，也可以用内存池管理节点，完全控制分配策略。在嵌入式环境、实时系统里，这种控制力是重要的。

第三个场景是学习本身的价值。堆的调整逻辑，也就是上浮和下沉，几乎可以说是二叉树的入门必修课。真正写过一遍，你才能理解为什么 priority_queue 是 O(log n)，为什么可以做到原地堆排序。这个底层逻辑，在后续接触红黑树、跳表、B+ 树时都会有很大帮助。

3.2 上浮与下沉：堆调整的两个基本动作

在动手写完整实现前，得先搞清楚两个最基本的操作。这个我建议重点理解，因为整个堆的全部逻辑就是这两个操作反复用。

上浮（sift up）：当一个新元素被放到数组末尾时，它可能破坏了堆的性质——它比它的父节点小（最小堆情形）。此时把它和父节点比较，如果它更小，就和父节点交换位置，然后继续向上比较，直到满足堆性质或到达根节点。让新节点“爬”上去，这就是上浮。举个例子，数组 [2, 5, 3, 8]，往末尾插入 1，此时 1 的父节点是 5，交换；1 的新父节点是 2，交换，最终变成 [1, 2, 3, 8]。上浮一次最多比较树的高度次，也就是 O(log n)。

下沉（sift down）：当堆顶元素被拿走，我们会把数组末尾的元素挪到根位置，这时候根元素可能比它的子节点大，破坏了最小堆性质。此时把它和两个子节点中较小的那个比较，如果它更大就交换，然后继续向下交换，直到满足堆性质或到达叶子。下沉也同样是 O(log n)。构建堆时用到的 heapify 操作，本质就是对所有非叶子节点执行一次下沉，从最后一个非叶子节点开始，一直下沉到根节点。

必须注意，在最小堆里，上浮是“如果当前节点比父节点小，就交换”，下沉是“如果当前节点比子节点大，就交换”。这两个规则方向别搞反，尤其是写代码时容易把下沉的交换条件写成“比子节点小就交换”，那样堆序就完全乱了。

3.3 完整实现：插入、删除、构建、堆排序

下面我给出一个手工最小堆的完整实现，用一个动态数组作为底层存储。这个实现我认为是“面试和工程之间比较平衡”的版本，既完整又不过度复杂：

#include <vector> #include <stdexcept> #include <iostream> class MinHeap { private: std::vector<int> data; // 父节点下标 int parent(int i) { return (i - 1) / 2; } // 左孩子下标 int left(int i) { return 2 * i + 1; } // 右孩子下标 int right(int i) { return 2 * i + 2; } // 上浮：从当前节点一直向上调整 void siftUp(int i) { while (i > 0 && data[i] < data[parent(i)]) { std::swap(data[i], data[parent(i)]); i = parent(i); } } // 下沉：从当前节点一直向下调整 void siftDown(int i) { int n = data.size(); while (true) { int smallest = i; int l = left(i); int r = right(i); if (l < n && data[l] < data[smallest]) smallest = l; if (r < n && data[r] < data[smallest]) smallest = r; if (smallest == i) break; std::swap(data[i], data[smallest]); i = smallest; } } public: MinHeap() = default; // 用一个数组构建堆，复杂度 O(n) MinHeap(const std::vector<int>& arr) : data(arr) { // 从最后一个非叶子节点开始向下调整 for (int i = data.size() / 2 - 1; i >= 0; --i) { siftDown(i); } } void push(int val) { data.push_back(val); siftUp(data.size() - 1); } int pop() { if (data.empty()) throw std::runtime_error("heap is empty"); int top = data[0]; data[0] = data.back(); data.pop_back(); if (!data.empty()) siftDown(0); return top; } int top() const { if (data.empty()) throw std::runtime_error("heap is empty"); return data[0]; } size_t size() const { return data.size(); } bool empty() const { return data.empty(); } // 返回底层的数组，便于外部访问 const std::vector<int>& getData() const { return data; } };

这个实现里最值得注意的地方是构建堆的循环：for (int i = data.size() / 2 - 1; i >= 0; --i)。为什么从size()/2 - 1开始？因为叶子节点不需要下沉，下标大于等于size()/2的节点都是叶子。从最后一个非叶子节点开始逐个下沉，每个节点最多下沉 O(log n) 次，总复杂度是 O(n) 而非 O(n log n)，这是个经典的数学结论。

堆排序用这个类也能很简单地实现，先把元素 push 进堆，再不断 pop，得到的就是升序序列。但如果要原地排序，就直接用标准库的 sort_heap：先 make_heap，再 sort_heap，整个数组原地变为升序。两种方式我都经常用，取决于是否需要保留原来的堆结构。

3.4 手工堆的性能与边界处理

手工实现堆的时候，我最在意的三个边界条件是：空堆的 pop 调用、数组中单个元素的下沉、以及下标计算的溢出。empty 判断是必须的，因为空堆的 top 和 pop 都会访问不存在的元素。单个元素时，siftDown 里的l < n和r < n会直接不成立，循环第一步就结束，这个逻辑天然安全。

下标使用 int 而不是 size_t，是我刻意为之。数组长度通常不会超过 int 范围，用 int 可以避免 size_t 无符号类型在 parent(0) 这种场景下产生负数下标的隐蔽 bug。如果你用 size_t 实现 parent(0)，(0 - 1) / 2会变成巨大的正数，导致灾难后果，这个细节错过一次就忘不了。

还有一个容易忽略的边界是动态数组扩容时的性能。如果 push 频率很高，vector 的自动扩容会带来多次元素拷贝。如果堆的元素是字符串、结构体等拷贝成本高的类型，建议提前 reserve 一定容量，或者干脆在构造函数里传入预期大小。比如我在日志模块里就预估了最多同时存多少条日志，然后提前 reserve，避免了大量中间扩容。

从复杂度上对比，push 和 pop 都是 O(log n)，top 是 O(1)，构建堆是 O(n)。这个数据是手写堆和库函数一致的，真正的差别在于常数因子：手写堆可以避免不必要的函数调用和比较器虚调度，在某些性能敏感场景下能快上 20% 到 30%，这个比例我在下面专门测试过。

4. 库函数 vs 手工实现：选型对照与踩坑实录

4.1 什么时候无脑用 priority_queue，什么时候必须手写

我做一个项目时，一般会先用一张小小的决策表来判断怎么选，它的逻辑其实就是回答三个问题：是否需要删除任意元素？是否需要修改堆内非堆顶元素的值？是否对堆操作的常数时间有极苛刻的要求？

大多数业务代码里，priority_queue 就是够用的。我之前做过一个负载均衡的模块，需要实时选择当前负载最低的节点，数据规模不大，用 priority_queue 加自定义比较器，整个模块写得非常清爽。只有当遇到“删任意元素”和“改堆内元素”这种端口不在标准库能力范围内时，才需要手写。这个判断标准很朴素：先问自己要不要删除堆顶以外的东西，要就手写，不要就库里拿。

4.2 七个我实际踩过的坑（含排查思路）

第一个坑是比较器方向写反。我前面提过，C++ 默认是最大堆，min-heap 需要自定义比较器 return a > b。但写着写着，手一滑就写回<了，结果是整个优先级完全逆序。排查思路很简单：打印取出的前几个元素，看看是不是期望的顺序。别问我为什么调了半小时才发现。

第二个坑是push_heap 前忘 push_back。标准库的 push_heap 只是“调整”而不是“插入”，它假定新元素已经在区间末尾。我曾经直接对向量调用 push_heap 而不先 push_back，导致最后一个元素以外乱套。这个问题会在堆的某个位置莫名其妙冒出一个无效值，排查起来很迷惑。所以我在项目里干脆封装了一个函数，把 push_back 和 push_heap 绑在一起，从根源上避免这种操作割裂。

第三个坑是自定义类型没有提供 < 运算符。当你写priority_queue<Task>而没有给 Task 定义比较方法时，编译器会报出一长串模板错误，往往指向operator<。这个时候别慌，看一眼错误信息最前面的“no match for operator<”就能确认问题。解决办法就是定义一个比较器结构体，或者给 Task 重载<。

第四个坑是使用完 sort_heap 后继续当堆用。sort_heap 会把数组变成完全升序，堆性质已经破坏。如果之后你对这个数组执行 pop_heap，行为是未定义的。这个问题常见于一些复杂的算法组合场景，比如先堆排序再想做点优先队列操作。我吃过一次亏之后，现在只要调用过 sort_heap，就在注释里明确写上“此数组已不再是堆”。

第五个坑是空堆调 top。这个属于基本功，但确实会犯。我早期在做一个定时器模块时，定时器全部到期后没有检查空堆就去取 top，直接崩溃。后来我在所有调用 top/pop 前都检查 empty，并且用 assert 做双重保险。

第六个坑是手写堆的下沉只比较了一边。有些初学者写 siftDown 只跟左孩子比较，忽略了右孩子。这种代码在小数据量的时候可能碰巧正确，但一旦右孩子更小，堆序就会破坏。排查方法是构造一个“需要跟右孩子交换”的用例，比如 [5, 6, 3]，弹出堆顶后，看最后的结果是不是仍然是合法最小堆。

第七个坑是性能测试被 debug 模式误导。用标准库堆相比手写堆的性能差异，在 debug 模式下会被放大，因为迭代器调试和模板层数带来了额外开销。真正做选型对比时，一定用 release 模式，开启优化后数据才有参考价值。

4.3 性能对比：常量和缓存友好性的真实影响

我在一个模拟任务调度的项目里，对 priority_queue 和手写堆做了一个简单的基准测试：先向堆里插入 100 万个随机整数，再全部弹出。release 模式下，手写最小堆比 priority_queue 快大约 15% 到 25%，priority_queue 又比 sort 后线性取极值快一个数量级以上。但是注意，这个差距很大程度来自于 priority_queue 的模板封装和比较器调用层级，而不是堆算法本身的差异。

在缓存友好性上，二者底层都是 vector 连续内存，所以区别不大。真正有区别的是“手写堆使用定长数组”的情况：定长数组通常能一次分配全部内存，并且把整个堆都留在 cache 里，而 vector 扩容后涉及旧内存释放和新内存拷贝，cache 命中率就下降了。所以如果你的堆大小是已知而且相对固定的，手写定长数组版本往往性能最优。在我的定时器模块里，就是把堆做成固定大小 1024 的数组，每次操作的开销非常稳定。

另一个容易被忽略的性能点是“比较器的拷贝代价”。priority_queue 的自定义比较器会被存储为容器的一个成员对象，如果你的比较器内部持有复杂状态，拷贝代价就会反映到每次 push/pop 中。手写堆可以直接用函数指针或者内联函数，把这个成本降到零。不过，对绝大多数业务系统来说，这些差异远没到瓶颈的程度，性能之外的代码可维护性往往更值得考虑。

5. 堆的内功心法：五个来自实战的进阶技巧

先讲一个小技巧：用堆和懒删除来处理“需要删除但不想维护索引”的场景。当你实在不想手写堆，但又需要删除任意元素时，可以往堆里再推入一个标记元素，表示“这个元素已删除”。真正弹出堆顶时，检查标记并丢弃。这种做法的缺点是死数据会堆积，所以需要定期重建整个堆。我一般设定一个阈值，比如堆大小超过实际元素数量的 2 倍时，就重新构建一次。这种方式写起来快，但因为无法删任意旧元素，只适合删除“当前堆顶”这种场景。如果删除位置很随意，代价就大了。

第二个技巧：大顶堆 + 小顶堆求中位数的组合结构。这是我在做监控系统耗时百分位数时反复用到的。维护两个堆，max_heap 存较小的一半，min_heap 存较大的一半，保持 max_heap.size() 不小于 min_heap.size() 且差值不超过 1。插入时比较新值和 max_heap.top()，决定塞进哪一边，然后平衡两边大小。中位数可以直接取 max_heap.top()，复杂度 O(1)。这个结构看起来简单，但插入的平衡逻辑里细节很多，建议至少自己实现一次，比背模板管用。

第三个技巧是手写堆配合 index map 实现 Dijkstra 的堆优化。在很多图算法里，节点距离更新以后，需要快速在堆里找到该节点并调整它的位置。具体做法是让堆里存的不是值本身，而是“节点编号 + 当前距离”，同时维护一个数组 index_map，记录每个节点在堆数组中的下标。当需要更新某个节点的距离时，用 index_map 找到它的位置，直接修改距离，然后根据新旧距离的方向对上浮或下沉。这个操作通常叫 decrease-key 或 increase-key，是手写堆相对标准库最大的优势。

第四个技巧是**“堆的原地数组化”能让调试变得更直观**。手写堆的底层就是一个 vector，我在调试时经常直接把整个 vector 打印出来，检查下标的父子关系是否成立。对于 priority_queue，由于没有迭代器，打印不了底层结构，只能一个个 pop 再 push 回去，麻烦得多。所以我做性能分析和正确性验证时，更倾向于先用 make_heap 的手动版本，验证通过后再封装成 priority_queue 适配器。

第五个技巧是构建堆时尽量用 make_heap 而不是逐元素 push。如果一开始就有一批量数据，直接 make_heap 是 O(n)，逐个 push 是 O(n log n)。数据量一大，差距会非常明显。我在做批量日志回放时，一万条日志直接用 make_heap 构建，一瞬间就完成了，而逐条 push 明显卡顿。所以只要不是真的“一条条到达的数据”，构建堆一定优先用批量接口。

6. 最后的经验：堆不是银弹，但它是你工具箱里的常备件

我在实际项目中用堆的时间越久，越觉得它本质上是在回答一个问题：如何用 O(log n) 的代价维护动态数据的优先级秩序。标准库把答案封装得很舒服，priority_queue 一行代码就能起一个优先队列；手工实现则把底层逻辑完整暴露出来，让你有能力去修改、去优化。两者不是替代关系，而是互为补充的两种武器。

如果你刚开始学，我的建议是先熟练使用 priority_queue，把自定义比较器、堆排序、Top K 这类基础场景全部刷一遍，然后立刻动手写一个最小堆。写完之后，再回过头去读标准库源码，你会发现那些模板代码突然变得很亲切。如果你已经有一定经验，建议找一个带 index map 的手写堆去练手，Dijkstra 堆优化也好，定时器管理也好，把这个能力掌握之后，你在需要精细控制数据结构的场合会从容很多。

没别的了，动手写代码去吧。堆这种东西，看十篇文章都不如自己 push 几个数进去然后 pop 出来，亲手感受一下它到底是怎么“上浮”和“下沉”的。