★ FEATURED ARTICLE 拿排序来说它是个能反复讲出花来的话题但你真让我挑一个“性价比最高”的排序实现我不会先选快排也不选归并而是会推荐小根堆。原因很实际在很多场景里我们根本不需要把所有数据完整排好只关心“当前最小的那个是谁”或者“前 K 个最小元素”。这时候小根堆几乎是唯一合理的答案——它既能在 O(1) 时间拿到最小值又能用 O(log n) 完成插入和删除而这些特性恰好是排序输出最底层的需求。我用 C 做小根堆排序输出不是一天两天了。从最早手写堆结构到后来直接用标准库的 priority_queue再到面试题里被反复问的 Top K 问题、合并 K 个有序链表、数据流中的中位数这些场景本质都在调用同一个能力用小根堆维护“最小值优先”的序列。这篇文章我就把这块技术彻底拆开从原理到实现从一行代码到手撸完整堆把我在实际项目中踩过的坑和总结出的经验全部写清楚。1. 小根堆的核心原理与排序输出的关系1.1 堆结构到底长什么样堆是一种完全二叉树底层用数组存储。所谓“完全二叉树”意思是除了最后一层其他层都是满的最后一层从左到右连续填充。这种紧凑结构带来的第一个优势就是不需要指针就能在数组里表达父子关系。对于下标 i 的节点它的左孩子是 2i1右孩子是 2i2父节点是 (i-1)/2。这三个公式是整个堆操作的基础。小根堆的关键约束是“堆序性质”对任意一个节点它的值必须小于等于它的所有后代节点。换句话说树根永远是整个堆里最小的元素。注意这里没有要求左子树和右子树之间有大小关系也没有要求同一层节点有序这是很多新手容易误解的地方。我试过用一个生活化的类比来解释小根堆想象一个会议现场最紧急的事情总是出现在讲台最前面但不是所有事情的紧急程度都严格排好了序——只要你知道哪件事最紧急就够了。堆只保证“根最小”不保证整棵树像排序数组那样严格有序。1.2 为什么排序输出要用小根堆排序输出最朴素的做法是先把数据全部收进数组调用 sort 排完再输出。这种方法的时间复杂度是 O(n log n)空间复杂度是 O(1)在数据一次性到齐的情况下已经很好。但有一类场景 sort 处理不了数据是动态产生的随时有新元素加入随时要取出当前最小值。如果每次插入都重新 sort代价是灾难性的。小根堆在这个场景下的表现是 O(log n) 插入、O(1) 取最小、O(log n) 删除最小。这意味着经过 n 次操作总复杂度仍然是 O(n log n)但数据不需要一次性到齐元素可以像水流一样不断注入和取出。我遇到过最典型的案例是某个日志系统日志消息按时间戳到达但需求是要按优先级输出高优先级先处理。无法预知后续消息的优先级又不能等全部收完再排序那就只有维护一个小根堆每来一条消息 push 一次系统每次处理时 pop 出当前最小优先级的消息。这个模式放在任何“流式数据按最小/最大优先输出”的场景里都成立。1.3 用优先队列做排序输出到底解决了什么问题优先队列是基于堆实现的抽象数据结构。C 的 std::priority_queue 默认是大根堆这经常让第一次接触的人踩坑——明明要输出最小元素结果 pop 出来的是最大值。做排序输出时如果发现元素顺序反了第一反应就应该是比较器方向错了。用优先队列做排序输出解决的三个核心痛点是无需提前知道数据总量动态插入删除只需要关注极值不需要维护全序列有序复杂度稳定无论数据有序还是逆序每次操作都是确定的对数时间1.4 手动建堆和标准库选哪个我的建议分两种情况。如果只是工程应用直接用 std::priority_queue它经过充分优化代码简洁不易出错。如果是学习原理、面试手写算法场景或者需要自定义堆操作比如堆的任意位置删除那必须能手写堆。这两条路我都会详细讲因为只有理解底层原理才能真正驾驭标准库的众多模板参数。2. 标准库 priority_queue 实现小根堆排序输出2.1 核心代码三行就能搭建排序输出框架标准库的小根堆定义如下#include iostream #include queue #include vector int main() { std::priority_queueint, std::vectorint, std::greaterint min_heap; std::vectorint data {42, 17, 9, 23, 100, 55, 1, 88}; for (int x : data) { min_heap.push(x); } while (!min_heap.empty()) { std::cout min_heap.top() ; min_heap.pop(); } std::cout std::endl; // 输出: 1 9 17 23 42 55 88 100 }核心就这一步第三个模板参数 std::greater 决定这是一个小根堆。为什么默认不这样因为 std::priority_queue 的默认比较器是 std::less 它让“最大元素”处于堆顶符合“优先级最高”的习惯认知。而 std::greater 把比较语义反过来变成了“最小值优先”。这里有个容易混淆的点std::greater 在 sort 里是用来做降序排序的很多人想当然以为 priority_queue 配 greater 也是降序结果输出和自己的预期完全相反。实际上 priority_queue 的比较器不是描述“顺序”而是描述“堆顶优先级”。提示priority_queue 的比较器表达的是优先级规则less 意味着值越大优先级越高greater 意味着值越小优先级越高。这是和 sort 比较器最大的区别。2.2 自定义类型怎么排序工程里很少只有 int更多是结构体。比如我有一个任务对象包含执行时间和优先级希望按执行时间最小的任务先输出代码这样写struct Task { std::string name; int execution_time; int priority; }; struct TaskTimeCompare { bool operator()(const Task lhs, const Task rhs) const { return lhs.execution_time rhs.execution_time; } }; std::priority_queueTask, std::vectorTask, TaskTimeCompare task_queue;注意这里比较器实现的逻辑当 lhs.execution_time rhs.execution_time 时返回 true。在优先队列的语义里返回 true 表示 lhs 的优先级低于 rhs也就是说执行时间较大的反而优先级低执行时间最小的会被放在堆顶。这个“反向思维”是很多初学者卡壳的地方。还可以用 lambda 表达式简化auto cmp [](const Task lhs, const Task rhs) { return lhs.execution_time rhs.execution_time; }; std::priority_queueTask, std::vectorTask, decltype(cmp) task_queue(cmp);这种做法在 C11 之后支持好处是逻辑直接写在定义处不需要单独声明一个仿函数结构体。缺点是无法跨函数复用只在局部推荐使用。2.3 排序输出的完整流程与复杂度分析用优先队列做排序输出的完整流程分两步将所有元素依次 push 建堆。反复 top 取出最小值并 pop直到堆为空。建堆过程如果用逐个 push时间复杂度是 O(n log n)。但如果你一开始就有完整的数组批量建堆可以做到 O(n)这是标准库的 priority_queue 不方便直接做到的——它没有提供接收迭代器范围的构造方式这一点在我使用的 C 标准版本中确实如此。所以我常用的策略是数据完整时先放 vector 里用 std::make_heap 系列函数建堆走 C 堆算法路线数据动态到达时用 priority_queue 逐个 push。两种策略的本质相同后者更贴近工程前者更贴近算法底层。整个排序输出的总复杂度仍然是 O(n log n)但常数上隐含一个额外系数因为堆排序的插入删除循环比快速排序的平均常数要大。实测下来在数据量百万级别以下差距不明显到了千万级、亿级快排通常更快。但堆的优势从来不是绝对速度而是动态性和稳定性所以选型时必须先想清楚数据呈现方式。3. 手写一个小根堆的完整实现3.1 类的设计与基础接口我建议所有准备面试或者深入理解数据结构的开发者都亲自动手实现一遍堆。这里我给出一个完整但精简的实现包含常用的 push、pop、top、size、empty 接口。template typename T class MinHeap { private: std::vectorT data; void siftUp(int idx) { while (idx 0) { int parent (idx - 1) / 2; if (data[idx] data[parent]) { std::swap(data[idx], data[parent]); idx parent; } else { break; } } } void siftDown(int idx) { int n data.size(); while (true) { int left 2 * idx 1; if (left n) break; int right left 1; int smallest idx; if (data[left] data[smallest]) { smallest left; } if (right n data[right] data[smallest]) { smallest right; } if (smallest idx) break; std::swap(data[idx], data[smallest]); idx smallest; } } public: void push(const T value) { data.push_back(value); siftUp(data.size() - 1); } void pop() { if (data.empty()) return; data[0] data.back(); data.pop_back(); if (!data.empty()) { siftDown(0); } } const T top() const { if (data.empty()) { throw std::out_of_range(heap is empty); } return data[0]; } size_t size() const { return data.size(); } bool empty() const { return data.empty(); } };3.2 siftUp 和 siftDown 的细节解析siftUp 处理的是新元素插入堆尾后的恢复操作。新元素进入数组末尾后它的位置可能破坏堆序性质因为它可能比自己的父节点还小。这时只需沿父链向上比较交换直到父节点比它小或者到达根节点。siftDown 处理的是堆顶被删除后的恢复操作。删除堆顶时我把最后一个元素搬到根位置然后把原来根的孩子中较小的那个和它比较如果比孩子大就交换继续向下走。这里有个关键细节要选择两个子节点中更小的那个来比较交换。为什么要选更小的孩子因为堆只要求“父小于等于子”如果我把较大的孩子换上来另一个更小的孩子反而可能小于父节点堆序又被破坏。而选更小的孩子交换能保证交换后父节点小于等于另一个孩子性质重新恢复。这个细节我见过太多人在手写时出错。3.3 批量建堆O(n) 的堆构建方法如果一开始就有完整的数组逐个 push 是 O(n log n)但正确的批量建堆只需 O(n)。方法是从最后一个非叶子节点开始倒序对每个节点执行 siftDown。MinHeap(const std::vectorT arr) { data arr; int n data.size(); for (int i (n - 2) / 2; i 0; --i) { siftDown(i); } }最后一个非叶子节点怎么算最后一个节点下标是 n-1它的父节点是 ((n-1)-1)/2化简就是 (n-2)/2。从这个节点开始向前逐个 siftDown。为什么是 O(n)直观理解是越靠近树底的节点siftDown 需要下降的层数越少而底层节点数量又最多。把每一层的节点数乘下降高度加起来最后得到的是一个收敛于 2n 的级数所以是线性复杂度。这个结论在面试里经常被追问到我建议你能自己推导一遍而不是死记结论。3.4 手动堆实现排序输出的完整示例有了上面的 MinHeap排序输出就非常简单了#include iostream #include vector int main() { std::vectorint data {42, 17, 9, 23, 100, 55, 1, 88}; MinHeapint heap(data); while (!heap.empty()) { std::cout heap.top() ; heap.pop(); } std::cout std::endl; return 0; }这段代码的输出严格从小到大。我实际使用中发现手写堆相比标准库的优势不只在教学场景。比如你需要随时查看堆里第二小的元素、需要支持堆元素的任意删除、需要合并两个堆这些操作在 priority_queue 上不容易直接做但手写堆通过数组可以自由扩展。数组本身就是总览全局的工具。4. 堆排序 vs 优先队列排序两种输出的取舍之道4.1 经典堆排序算法经典的堆排序通常指原地排序思路是构建一个大根堆然后反复交换堆顶和堆末尾元素让最大值“沉底”堆的范围逐渐缩小最终数组从后往前依次放置最大元素得到升序序列。但如果用最小堆做堆排序输出的序列是降序排列的。这里就有一个容易混淆的现象用小根堆逐个 pop 得到的是升序序列但原地堆排序的小根堆版本得到降序序列。原因在于原地排序必须复用原数组空间每次 pop 把最小值放到数组前端时剩余堆的形态会受到影响不如大根堆原地排序方便。所以实际工程里做原地排序几乎都选大根堆。小根堆更常用于优先队列场景输出最小元素、动态处理流式数据。4.2 两种方式的实际性能差异我做过一个不算严谨但足够参考的测试对 1000 万个随机整数排序比较 std::priority_queue 逐个 push pop 的方式、std::sort 快速排序、手动实现堆排序三者的时间。快排最快堆排序居中priority_queue 构建排序最慢因为多次动态 vector 扩容和函数调用开销更大。但排序输出如果只是“一次性把数据排好输出”那选择堆排序本身就不是最优的。堆存在的意义是“在任意时刻知道极值”不是“把全部数据排得整整齐齐”。这也是我经常跟人强调的一个观点优先队列不是免费的排序替代品而是另一种适用于动态数据场景的工具。把一次性排序交给 sort把动态最小/最大值输出交给堆这才是合理的分工。4.3 空间复杂度与数据规模的影响手写堆和 priority_queue 都基于 vector空间复杂度 O(n)没有额外存储。相比归并排序的 O(n) 额外空间堆排序是原地算法这一点在内存受限的嵌入式场景非常关键。但是要注意 vector 扩容带来的双内存开销。当 vector 容量不足时会申请一块更大的内存把旧数据拷贝过去再释放旧内存峰值内存可能是两倍。处理超大堆时可以预先调 reserve 预留容量避免频繁扩容std::priority_queueint, std::vectorint, std::greaterint heap; std::vectorint underlying; underlying.reserve(1000000); std::priority_queueint, std::vectorint, std::greaterint heap2( std::greaterint(), std::move(underlying));后一种写法是在构造时把预留好容量的 vector 直接作为底层容器。虽然实用性有限但峰值性能上有明显的提升。5. 核心应用场景与代码实战5.1 流式数据输出最小的 K 个元素经典面试题“给定一个数据流随时可能加入新整数随时需要输出当前已出现的最小 K 个数字。”我建议的解法是维护一个大根堆容量限制为 K。新元素来了如果堆未满直接 push如果堆已满与堆顶最大的元素比较小则替换。这样堆里始终维护当前最小的 K 个元素而且大根堆顶就是这 K 个中的最大值。这与本题的“小根堆排序输出”不同的是它利用了“大根堆”来做约束固定的 Top K。同样用小根堆也能做做法是所有元素都进小根堆每次 pop 出最小值直到取出 K 个但那样堆的规模会持续增大时空表现不如大根堆。从这个例子想说明的思路是小根堆擅长“取最小”大根堆擅长“选最大”实际问题中经常要组合使用理解堆本身比记住某个特定模板更重要。5.2 合并 K 个升序链表另一个典型场景有 K 个升序链表需要输出它们的合并升序序列。最直接方法是把所有节点放入小根堆每次 pop 输出一个节点再把这个节点的下一个节点 push 进堆。struct ListNode { int val; ListNode* next; }; struct Compare { bool operator()(ListNode* a, ListNode* b) const { return a-val b-val; } }; ListNode* mergeKLists(std::vectorListNode* lists) { std::priority_queueListNode*, std::vectorListNode*, Compare pq; for (ListNode* head : lists) { if (head) pq.push(head); } ListNode dummy; ListNode* cur dummy; while (!pq.empty()) { ListNode* node pq.top(); pq.pop(); cur-next node; cur node; if (node-next) { pq.push(node-next); } } return dummy.next; }这个算法每输出一个节点都从 K 个候选最小值中选出真正的全局最小值复杂度 O(N log K)N 是总节点数。你如果把 K 个链表换成 K 个有序数组、K 路归并排序完全是同一套逻辑。小根堆在这里不是锦上添花的优化而是解决这类合并问题的核心。5.3 Dijkstra 最短路中的排序输出场景图论里头最常用的优先队列案例就是 Dijkstra 算法。每次更新距离后把当前最短距离的节点放到堆顶优先处理。这里用小根堆维护“当前最小的未处理距离”本质上也是某种排序输出——它输出的每条边的处理顺序就是“按距离从小到大”。如果改成大根堆算法直接失效处理的就不是最近节点了。所以“排序输出”这个词不要理解得太窄。不仅仅是控制台打印排序结果任何“按某种优先级循环取极值”的逻辑都是在做一种广义的排序输出。5.4 数据流中位数动态数据的实时中位数是小根堆和大根堆配合使用的经典案例小根堆存较大的一半大根堆存较小的一半时刻保持两个堆的大小差距不超过 1插入时根据堆顶判断新元素归属然后调整两个堆的平衡。查询中位数时如果总数为奇数就直接取元素较多那个堆的堆顶偶数就取两堆顶平均值。这个结构就是我在前面反复强调的“组合使用”——一个堆只能给你极值两个堆的极值互相配合才能支撑更复杂的需求。6. 常见错误与性能排查实战6.1 比较器方向搞反这是 priority_queue 使用者最常踩的坑。std::greater 是“小根堆”std::less 是“大根堆”。很多从 Java 转过来的人会被搞晕因为 Java 的 PriorityQueue 默认也是小根堆而 C 默认是大根堆。我常用的一个记忆方法是看比较器的行为逻辑比较器返回 true 表示“第一个参数的优先级低于第二个参数”。那么对 std::greater 来说等于说“数值更大的优先级更低”因此值最小的在堆顶——这就是小根堆。6.2 手写堆时索引越界手写 siftDown 时最容易犯的错误是忘记检查右孩子是否存在。左孩子下标 left 2*idx1右孩子 right left1右孩子可能已经越界跳过数组末尾。如果不判断 right n其中 right 可能访问到数组外的内存结果是未定义行为有时表现为随机错误有时直接崩溃非常难排查。我自己调试时曾遇到一个诡异的现象同样数据在 Debug 下正常Release 下偶发错误顺序。最终定位就是右孩子越界访问编译器优化把未定义行为“还原成了错误”。这个经历提醒我所有数组下标检查都必须严谨绝不能靠运气。6.3 大量数据输入时的动态扩容影响如果预知数据规模较大建议提前 reserve。我没有做精确 benchmark但直观经验是当数据量在十万量级动态扩容带来的影响微乎其微千万量级时持续扩容和拷贝的耗时影响就比较明显了。解决办法很简单std::vectorint temp; temp.reserve(2000000); // 后续所有 push 都基于 reserve 过的容器6.4 小根堆 vs 快速排序的适用边界最后我列一个速查表帮助快速判断该用哪个工具场景推荐方案理由一次性全量排序std::sortO(n log n)常数小原地排序需要原地 O(1) 空间排序手写堆排序无额外空间开销动态流数据取最小小根堆 / priority_queue插入删除 O(log n)数据量极大但只需 Top K大小为 K 的堆内存 O(K)远小于全量顺序频繁变化取中位数大根堆 小根堆组合维护平衡O(1) 查询我在实际项目中体会最深的一点是调度系统、事件驱动系统、网络协议栈里维护“当前一条记录”或“下一件最重要的事”的场景远多于“把所有数据整体排一遍”这也是小根堆比快排在系统级代码里更常见的原因。6.5 从迭代器范围直接构造小根堆怎么处理priority_queue 没有提供“接收迭代器范围”的构造函数但 C 的堆算法可以直接操作 vectorstd::vectorint data {42, 17, 9, 23, 100, 55, 1, 88}; std::make_heap(data.begin(), data.end(), std::greaterint()); while (!data.empty()) { std::pop_heap(data.begin(), data.end(), std::greaterint()); std::cout data.back() ; data.pop_back(); }这套底层堆算法 make_heap、push_heap、pop_heap、sort_heap 功能和 priority_queue 重合但好处是能自由控制容器支持批量建堆还能直接和现有的 vector 数据交互。如果你既想要 priority_queue 的简洁接口又想保留 vector 的灵活性堆算法是很好的中间选项。7. 深入补充堆的自定义能力7.1 通过索引式存储实现特殊堆操作前面提到手写堆能支持任意位置删除。删除任意元素的做法是把该元素与堆尾元素交换pop 掉尾部然后根据新值和父节点的大小关系决定向上 siftUp 还是向下 siftDown。这个操作在迪杰斯特拉的堆优化版中有实际意义当某个节点的距离更新后需要调整它在堆中的位置。我常用一个额外数组 posMap 记录每个元素在堆数组中的下标这样能在 O(log n) 内找到任意元素并完成调整。加了 posMap 后堆就具备了修改任意元素的能力在很多图算法中都是必备的基础组件。7.2 斐波那契堆与二叉堆的取舍如果数据规模极大且需要频繁的 decrease-key 操作理论上斐波那契堆的均摊 O(1) 复杂度更优。但工程上我却极少用斐波那契堆——它实现复杂、常数巨大而且实际数据中 decrease-key 的分布往往并不均匀二叉堆的表现通常已经足够。这个选择的原则是复杂度分析给出上限工程经验告诉我们捷径。二叉堆 索引数组已经能覆盖绝大多数场景。7.3 多级优先级与小根堆结合的扩展现实中排序输出往往不只一个维度。比如一个任务既有 deadline又有优先级我希望优先输出 deadline 近的deadline 相同再比较优先级。这种多层优先级本质上就是构造一个组合比较器struct MultiCompare { bool operator()(const Task a, const Task b) const { if (a.deadline ! b.deadline) { return a.deadline b.deadline; } return a.priority b.priority; } };这段代码的含义仍然是“优先级规则”先比 deadline再比 priority。把这个比较器传给 priority_queue堆顶就是我最关心的那条任务。这个模式在任何有多维排序需求的系统中都能迁移使用。提示使用自定义比较器时务必保证比较规则是严格弱序的strict weak ordering。也就是说两个参数互换时结果必须相反且不能出现同时认为 a 优先于 b 又 b 优先于 a 的矛盾否则堆的操作结果不可预期。8. 小根堆排序输出的实践经验总结做小根堆排序输出了这么多次总结一下我个人在实操中最看重的几点第一优先队列默认大根堆这件事怎么强调都不为过。凡是发现输出顺序与预期完全相反第一反应就应该检查比较器。我见过不止一次因为默认构造 priority_queue 导致排序结果反了、Debug 到怀疑人生的案例。第二手写堆虽然麻烦但值得每个写 C 的开发者练一次。练 siftUp 和 siftDown 的过程实际是在练“数组下标与树结构之间映射”的直觉。这个直觉一旦建立理解堆排序、建立哈希索引、维护线段树都会顺畅很多。第三小根堆的应用不局限于排序输出本身。从 Top K 到流式中位数到 Dijkstra核心思维永远是“极值优先”。遇到系统需要不断筛选最优项的场景第一选择用它而不是反复排序。第四调试时要记得利用堆数组本身。我调试手写堆时通常在每次操作后打印整个 vector确认堆序性质是否还在。肉眼检查根节点和孩子的大小关系比黑盒调用 top 来得更直观。最后分享一个小技巧如果你看到编译器警告“comparison always true”或“comparison always false”多半是比较器写反了。这算是一个很省力的自查点。小根堆这个结构本身不算复杂但相关的最佳实践和踩坑点确实不少希望这篇分享能让你在实际开发中少走几步弯路。
阅读完成 · 觉得有帮助？
