做 TopK 需求的时候我一开始总习惯性先想std::sort把整张表排一遍然后取前 N 个。数据量到百万级以后每次跑都要多花几百毫秒心里总觉得亏——因为我真正用到的只是排好序结果里最前面的那几条。后来换成堆几十毫秒出结果再后来为了能在维护过程中修改堆内元素我又自己动手实现了一套小顶堆。这篇文章我就把这两条路线都讲透一条是调用标准库里的priority_queue和make_heap系列函数另一条是手工实现siftUp、siftDown与heapify。适合正在处理 TopK、调度器、图算法或者准备手写堆的读者参考。1. 堆到底是什么先搞清楚这棵“不完全随意的完全二叉树”1.1 堆的两条规则堆是一种特殊形态的二叉树它只有两条规则第一它必须是一棵完全二叉树也就是说除了最后一层其他层的节点都是满的最后一层从左到右连续填充第二它必须满足堆序性——如果每个父节点都不小于子节点那叫大顶堆堆顶就是全局最大值如果每个父节点都不大于子节点那叫小顶堆堆顶就是全局最小值。这两条规则缺一不可。完全二叉树保证了堆可以平铺在数组里存储而且不会浪费空间堆序性则保证了最值永远在堆顶并且插入、删除、取堆顶的时间复杂度都能维持在 O(log n)。很多人把堆和二叉搜索树搞混实际上两者的差别非常大二叉搜索树强调左小右大用来快速查找任意元素堆只强调父和子的相对大小用来快速拿到全局最值它不保证左子树和右子树之间有严格的大小关系。这也是为什么堆适合做优先队列而不是做查找表。1.2 数组里的父子关系下标就是指针堆用数组存储时父子关系不是通过指针串起来的而是通过下标计算出来的。以 0 起始的数组为例下标i的节点它的左孩子是2*i1右孩子是2*i2父节点是(i-1)/2。如果是 1 起始的下标那左孩子是2*i右孩子是2*i1父节点是i/2。两种约定各有拥趸但标准库和绝大多数工程代码都用 0 起始所以我建议你也默认用 0 起始省得换算出错。这个下标关系是堆的所有操作的地基。你后面写的siftUp、siftDown里面所有向上爬、向下沉的逻辑本质上都是在做下标运算。我见过不少手写堆翻车的案例最后定位下来都是左孩子2*i1写成了2*i或者父节点(i-1)/2和 1 起始的i/2混用了这种低级错误所以这个表值得先记住。关系0 起始下标1 起始下标左孩子2*i12*i右孩子2*i22*i1父节点(i-1)/2i/2最后一个非叶节点n/2-1n/21.3 先说清楚“堆能解决什么问题”在进入代码之前有必要把使用场景摆出来因为很多人是用到哪查到哪最后发现这个场景其实用别的结构更合适。堆最经典的四个用途一是前 K 大/前 K 小用一个容量为 K 的小顶堆遍历数据堆里留的就是前 K 大二是中位数用一个大顶堆存较小的一半、一个小顶堆存较大的一半两个堆的大小差不超过 1堆顶之和平均一下就是中位数三是合并 K 个有序序列每次从 K 个序列的当前头部里取最小堆帮你在 O(log K) 内找到下一个该输出的元素四是带优先级的任务调度比如定时器按过期时间建小顶堆到期时间最近的任务始终在堆顶。这四个场景看起来五花八门本质都是同一个诉求动态集合里反复取最值。如果集合是写死的那排序一次取头尾就行如果数据是动态增删的每来一个就排一次队代价就上去了堆正好能不重排序地维护最值在顶部这个状态。2. 标准库方案priority_queue 与堆算法组合拳2.1 三行代码入门大顶堆的默认姿势C 标准库最直接的堆封装是std::priority_queue它属于容器适配器底层默认用std::vector存数据对内封装好堆的调整逻辑。先看最基础的大顶堆用法#include queue #include iostream int main() { std::priority_queueint pq; pq.push(3); pq.push(1); pq.push(4); pq.push(1); pq.push(5); std::cout pq.top() \n; // 5 pq.pop(); // 弹出 5pop 不返回值 std::cout pq.top() \n; // 4 return 0; }这段代码最需要记住的是pop()不返回被弹出的元素。标准库设计成这样是因为返回引用的话弹出去之后引用立刻失效容易诱发悬垂引用直接返回值又涉及临时副本的拷贝成本。所以正确的姿势永远是先top()取值再pop()弹出。很多新手第一次用会下意识写int x pq.pop();然后一脸疑惑地看编译报错。如果你要的是小顶堆模板参数要稍微变一下#include functional std::priority_queueint, std::vectorint, std::greaterint min_pq;第三个模板参数是比较器传std::greaterint之后堆顶变成最小值。注意greater需要包含functional头文件虽然很多环境下queue会间接包含但显式包含才是稳妥的做法。2.2 自定义比较器less 和 greater 的直觉陷阱自定义类型使用priority_queue时最常见的坑就是比较器方向搞反。这里有一个非常反直觉的事实默认比较器std::lessint造出的是大顶堆std::greaterint造出的是小顶堆。它的底层逻辑是优先级队列里的优先级高定义为更大——在less的比较语义下a b为真意味着b更大于是b往堆顶挤最后堆顶是最大元素。很多人在自定义仿函数时也会栽在这里。我直接给你一条能落地的心法仿函数返回true的那个对象会被当作优先级更低的那一方往堆下方沉。举个例子假设要按任务的截止时间排序越紧急的越先处理也就是 deadline 越小优先级越高struct Task { int deadline; std::string name; }; struct TaskCmp { bool operator()(const Task a, const Task b) const { // 当 a 的截止时间更晚时认为 a 优先级更低 return a.deadline b.deadline; } }; std::priority_queueTask, std::vectorTask, TaskCmp task_queue;这段代码里return a.deadline b.deadline的意思是如果a的 deadline 比b大那a的优先级就更低应该沉下去。最终堆顶就是 deadline 最小的那个任务。这个心法比死记反着写要靠谱因为你一旦面对三层嵌套的排序规则反着写三个字完全不够用。2.3 make_heap 系列更底层的裸堆操纵priority_queue用起来方便但它把底层容器藏得太严实了无法遍历、无法直接访问内部数组、无法精细控制内存。如果你需要这些能力标准库还提供了一套操作在迭代器上的堆算法make_heap、push_heap、pop_heap、sort_heap、is_heap。它们直接作用在vector上让你拿到裸堆的控制权。#include algorithm #include vector std::vectorint v {3, 1, 4, 1, 5, 9, 2, 6}; std::make_heap(v.begin(), v.end()); // 原地建大顶堆v[0] 是最大值 int max_value v.front(); std::pop_heap(v.begin(), v.end()); // 把堆顶挪到数组末尾 int popped v.back(); // 被弹出的最大值 v.pop_back(); // 真正从容器里移走 v.push_back(7); // 先尾插新元素 std::push_heap(v.begin(), v.end()); // 再调整让新元素进入堆序 bool ok std::is_heap(v.begin(), v.end()); // 检查当前是否满足堆序 std::sort_heap(v.begin(), v.end()); // 堆排序默认升序这套接口的好处是你可以随时看一眼容器里的全部元素坏处是必须严格遵守先插入到容器尾部再调用push_heap和先调用pop_heap再pop_back移除尾部的操作顺序。顺序一旦颠倒堆序性就被破坏了而且不会报错只会默默产出错误结果。这也是我不建议新手一上来就玩make_heap的原因它比priority_queue更透明也更容易误用。2.4 库函数的高频踩坑位先说一个所有人迟早会遇到的问题top()返回的是const引用。这意味着你不能通过pq.top()直接修改堆顶元素的值。如果你尝试拿到引用再改逻辑上会破坏堆序接口层面也根本不让你改。有些场景确实需要修改某元素比如 Dijkstra 算法里更新了距离此时priority_queue的正规做法是惰性删除新的更优值重新push进去堆里留着旧值弹出时发现元素过期就弃掉。这个技巧我在第四节还会细说。第二个坑是扩容问题。priority_queue底层是vector反复push会触发多次扩容而扩容的开销比很多人想象的大。标准库没有给priority_queue提供reserve接口但你可以先对底层容器做预留再把它移动进队列std::vectorint bucket; bucket.reserve(1000000); std::priority_queueint, std::vectorint pq(std::lessint(), std::move(bucket));这个写法看起来有点怪但恰好利用priority_queue的构造函数它接受比较器和容器初值。数据量大的场景能明显减少 reallocation 带来的开销。第三个坑是自定义比较器与top()的稳定性。堆排序和优先队列都是不稳定的值相同的两个元素谁先谁后没有保证。如果你的业务依赖同优先级内部的先后顺序你需要给元素额外塞一个自增序号做次级排序键不要指望标准库堆给你稳定序。3. 手工实现堆siftUp、siftDown 与 O(n) 建堆3.1 两个核心动作的分工读源码也好自己写也好堆调整的原子动作只有两个上浮siftUp和下沉siftDown。上浮用于向堆尾插入新元素后让新元素一路往上找位置下沉用于堆顶被移除后把新的堆顶元素往下找位置也用于把任意一个不守规矩的节点拉回正确位置。这两个动作重要程度并不对等。插入操作只需要上浮但弹出、替换、建堆这三种核心操作全都依赖下沉。尤其是建堆只有靠下沉才能做到 O(n) 的复杂度靠上浮逐个插入是 O(n log n)。所以如果你只想记一个动作优先把siftDown写熟、写对。写siftDown时最容易出的问题有两个一是循环里没判断左右孩子的下标是否越界导致访问到容器末尾之外的垃圾数据二是用size_t做循环变量时下标递减到 -1 会变成一个巨大的无符号数循环直接失控。第一个问题靠l n和r n的显式判断解决第二个问题建议循环变量用int或者写while (i 0)这种能安全退出到 0 的结构。3.2 一个可以直接抄的小顶堆模板下面这个模板类是我自己用的最小实现大顶堆只需要把sift_up和sift_down里的比较符号反向即可。代码走的是交换路线好处是逻辑直白适合做教学和入门对性能有执念的读者看完整片再考虑换成滑动赋值。#include vector #include utility #include cstddef template typename T, typename Container std::vectorT class MiniHeap { public: size_t size() const { return c.size(); } bool empty() const { return c.empty(); } const T top() const { return c.front(); } void push(const T val) { c.push_back(val); sift_up(c.size() - 1); } void push(T val) { c.push_back(std::move(val)); sift_up(c.size() - 1); } void pop() { if (empty()) return; std::swap(c.front(), c.back()); c.pop_back(); if (!empty()) sift_down(0); } // 用 val 替换堆顶然后下沉调整 void replace(const T val) { c[0] val; sift_down(0); } private: Container c; void sift_up(size_t i) { while (i 0) { size_t parent (i - 1) / 2; if (c[parent] c[i]) break; std::swap(c[parent], c[i]); i parent; } } void sift_down(size_t i) { size_t n c.size(); while (true) { size_t left 2 * i 1; size_t right 2 * i 2; size_t smallest i; if (left n c[left] c[smallest]) smallest left; if (right n c[right] c[smallest]) smallest right; if (smallest i) break; std::swap(c[i], c[smallest]); i smallest; } } };这个类只暴露了最核心的四个方法。pop()的内部流程是先把堆顶换到尾部然后pop_back()最后让原来的尾部元素从堆顶下沉。这里的std::swap配合pop_back()有一个好处即使元素类型是复杂对象也不会产生额外的析构或者拷贝负担交换之后尾部那个旧堆顶被正常销毁堆内其他元素保持原对象。3.3 replaceTopTopK 场景省一半开销我实现的replace方法在 TopK 场景里特别有用。先看传统写法数据比堆顶大时你要先pop()再push()这两步各做一次 O(log K) 的调整如果写成replace直接拿新值覆盖堆顶然后只做一次下沉O(log K) 完成全部工作。数学上没有本质区别但常数差距是实打实的数据量几千万时肉眼可见。TopK 的标准模板长这样MiniHeapint min_heap; // 容量最多 K小顶堆 for (int x : data) { if (min_heap.size() K) { min_heap.push(x); } else if (x min_heap.top()) { min_heap.replace(x); } } // min_heap 里存的就是前 K 大这里用堆的直觉是小顶堆堆顶是堆内最小元素也是进入前 K 的门槛。新元素只有比门槛高才有资格挤进来。每次挤进来都会把门槛抬高遍历完整个序列堆里剩的自然就是最大的 K 个。再说一个细节如果replace用std::swap风格实现则需要额外处理原堆顶对象怎么销毁的问题。我上面的实现是直接c[0] val需要类型具备赋值能力但对于大多数场景就够了。你也可以用移动赋值c[0] std::move(new_val);可以避免拷贝。3.4 heapify 与堆排序O(n) 建堆的直觉建堆有两种路径。一种是从空堆开始逐个push每个元素上浮 O(log n)总代价 O(n log n)。另一种是一次性把数据放进数组然后从最后一个非叶节点开始往前逐个下沉这就是make_heap的原理总代价 O(n)。初次接触的人很难相信 O(n) 这个结论因为直觉是几乎每个节点都要动画怎么可能线性。关键点在于从最后一个非叶节点往前下沉意味着每个节点的下沉距离等于它的高度而大多数节点都在树的底层高度很小。底下一半的节点高度是 0 或 1根本不需要动越往上节点越少每往上一层数量减半下沉距离只增加 1。这个数量减半、距离微增的组合求和结果收敛到常数乘以 n所以总工作量是线性的。至少比每个节点都从根部走一遍的朴素直觉要省得多。完整的手写 heapify 和堆排序代码如下void make_heap_bottom_up(int* arr, size_t n) { // 最后一个非叶节点是 n/2-1往前循环到 0 for (int i (int)(n / 2) - 1; i 0; --i) { sift_down(arr, n, i); } } void sift_down(int* arr, size_t n, size_t i) { while (true) { size_t left 2 * i 1; size_t right 2 * i 2; size_t largest i; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest i) break; std::swap(arr[i], arr[largest]); i largest; } } void heap_sort(int* arr, size_t n) { make_heap_bottom_up(arr, n); for (size_t len n; len 1; --len) { std::swap(arr[0], arr[len - 1]); sift_down(arr, len - 1, 0); } }注意这里的循环变量i用的是int因为n/2-1在n0时会变成 -1如果写成size_t就变成无穷大循环了。另外heap_sort是原地排序空间复杂度 O(1)这是它和归并排序相比最大的优势可惜稳定性和常数让它通常打不过经过高度优化的std::sort所以工程上很少有人拿手写堆排序当日常工具它更多是出现在面试和教学里。4. 选型与实测什么时候该调库什么时候该手写4.1 标准库罩不住的需求清单标准库很好但它不是万能的。我总结了几类必须考虑手工实现堆的场景你可以对照自己的业务看。第一类是需要 decrease-key / increase-key 的场景。最典型的是 Dijkstra 最短路径算法松弛边之后要更新一个已经进堆的节点的距离。priority_queue不支持这种操作所以工程上常见两种绕法要么用惰性删除也就是更新距离后重新push进去弹出时发现旧记录过期就丢弃要么自己写一个小顶堆额外维护一张节点在数组中的下标映射表更新节点值时同步改映射然后从该位置向上或向下调整。前者代码简单但堆里会积压过期记录后者代码复杂但时间和空间都更干净。第二类是需要遍历堆内元素的场景。priority_queue刻意隐藏了底层容器遍历不了。如果你做的是调试器、任务监控面板需要定期把堆里所有任务打出来看看用手写堆配合std::vector就舒服多了直接遍历数组即可还记得堆序性质保证数组某些前缀满足部分有序。第三类是需要删除任意元素的场景。标准库堆只支持删堆顶手工堆配合映射表可以在 O(log n) 内删除任意节点把目标节点换到数组尾部再根据父子和当前位置的关系决定上浮还是下沉。这种操作在带优先级的资源调度器里非常常见比如撤销一个还未执行的定时任务。第四类其实不算需求而是心理预期对代码绝对掌控。标准库实现要考虑所有类型泛型层数多但换个角度讲它也可能为了通用性牺牲一点常数。自己写一个只服务你特定类型的专版堆代码少、逻辑直白性能上往往还能快一截。4.2 同一个 TopK 问题四条路线的实测对比我在某台普通开发机上做过一个小测试生成的 100 万个随机int找出前 100 大开 O2 编译四种写法的大致耗时如下。你不是为了拿这个数字去跟别人对线而是看它们之间的相对差距。方案大致耗时说明std::sort全量排序约 100~120 ms简单但冗余白排了 99.99% 的数据std::make_heap 逐步pop_heap100 次约 20~30 ms一次 O(n) 建堆后只弹 100 次std::priority_queue遍历 TopK约 25~35 ms写法最稳适合流式数据手写小顶堆 replace约 15~25 ms省一次poppush需要自己写对从这个表能读出的信息量比谁快谁慢更大。第一全量排序在 Top 类问题上确实性价比低数据量越大差距越夸张第二priority_queue和手写堆之间没有质的差距手写堆赢在省掉了pop之后再一次push的两次调整变成了单次replace的一次调整第三数据规模如果只有几千上面这些差距可以忽略选方案的时候应该优先考虑代码可读性和维护成本而不是那几微秒。4.3 我的工程习惯与最后几条建议我自己的默认选项是优先用priority_queue。它简单、可靠、代码审查的人一眼能看懂。只有出现下面三种情况我才会换手写堆堆内元素需要频繁修改且无法用惰性删除将就、需要遍历堆内全部元素、或者明确用 profile 验证了priority_queue是瓶颈所在。如果真要手写我给几条实战建议。第一建议在类内部额外维护一个size_t的成员来表示逻辑长度不要把数组长度和堆长度混为一谈否则做堆排序或者分块处理时很容易越界。第二交换节点时如果元素是自定义对象用std::swap或移动赋值而不是拷贝不然大量字符串、容器对象会白白多出拷贝开销。第三写完堆之后一定要跑随机化测试随机插入再逐个弹出验证弹出的顺序严格递增或递减尤其要测n1和n2这种边界很多实现都在这种小规模输入上暴露问题。最后分享一个我在实际项目里常用的技巧当priority_queue需要惰性删除时我通常会在元素结构体里加一个version字段每次 push 新纪录时 version 自增弹出时对比当前堆顶的 version 和最新的全局 version不匹配就直接丢弃并继续弹。这个技巧比弹出去之后再检查过期效率更高而且不容易漏处理。用堆这件事很多时候图的不是我会不会写而是我的方案能不能被半年后的自己一眼看明白。能调库把逻辑写清楚就别急着从头造轮子真到了要手写的地步再按我上面说的几个边界条件仔细打磨。