堆排序这道题我在带新人的时候几乎每轮都会拿出来讲一次。原因很实际它是少数几个能把“数组下标运算”“树形结构”“复杂度推导”三件事一次性串起来的基础算法而“用小根堆实现堆排序”这个看起来平平无奇的每日一题恰好把其中最容易翻车的环节全暴露了——建堆到底从哪个下标开始、下滤的时候跟谁比、交换之后堆的范围怎么缩、为什么明明写的是小根堆跑出来的却是一个降序数组。这些疑问我在第一次手写的时候全踩过而且不止一次。这篇就把小根堆实现堆排序的完整思路、两种语言的代码实现、我自己踩过的坑以及实测的性能感受摊开来讲代码给 Python 和 Java 两版C 标准库那几个函数的行为差异单独拎出来说。适合正在刷基础题、想把算法底子打牢的同学也适合工作几年后回头把这块知识重新捋一遍的朋友——毕竟面试里手写堆排序考察的从来不是“你会不会背”而是“你清不清楚每一步为什么这么走”。1. 小根堆到底是个什么东西1.1 两条硬性规则和数组下标的对应关系小根堆的定义只有两条但这两条必须同时满足第一它是一棵完全二叉树除了最后一层其余各层都是满的最后一层的节点全部靠左排布第二任意一个节点的值都不大于它左右孩子的值。注意第二条只约束“父子之间”兄弟之间、堂兄弟之间没有任何大小关系这一点是很多人理解堆时的第一个误区——堆不是二叉搜索树它没有中序遍历有序这种性质。为什么要求“完全二叉树”这不是为了好看而是为了让这棵树能直接塞进一个数组且不浪费任何空间。完全二叉树的性质保证了如果按层序把节点依次放进数组那么下标为 i 的节点它的左孩子下标一定是 2i1右孩子是 2i2父节点是 (i-1)/2 向下取整。这三条公式必须背到条件反射的程度后面所有代码都绕着它们转。关系公式举例i3左孩子2i 17右孩子2i 28父节点(i - 1) // 21是否有左孩子2i 1 n7 n 时成立是否为叶子2i 1 n7 n 时是叶子拿一个具体数组举例[5, 9, 3, 12, 8, 7, 1]长度 7。下标 0 的 5 有两个孩子下标 1 的 9 和下标 2 的 3下标 2 的 3 有两个孩子下标 5 的 7 和下标 6 的 1。这个数组当前并不是堆因为 5 比它的孩子 3 大9 比它的孩子 8 大两处违规。所谓“建堆”就是通过一系列局部调整把这个数组修成一棵合法的小根堆。1.2 为什么用数组而不是指针树刚学数据结构的时候很多人第一反应是用节点加左右指针来搭这棵树写起来直观。但真到堆这个场景指针结构基本是负分。原因有三个每一个都跟常数因子有关。第一个是内存局部性。数组在内存里是连续的一段CPU 缓存按行加载你访问下标 i 的时候2i1 和 2i2 大概率已经在缓存里或者就在附近访问代价很低。指针树的节点散落在堆内存各处每次跳转都可能是一次缓存未命中在数据量大、循环次数多的情况下这个差距会被放大到很明显的程度。第二个是空间开销。指针树每个节点要额外存两个指针64 位下就是 16 字节还要加上对象头、对齐填充。一个一百万的堆光指针就多出十几兆而数组版一行int[] a new int[n]就完事了除了元素本身没有任何额外开销。第三个是代码复杂度。数组版不需要处理 null、不需要递归、不需要释放内存下滤就是一个 while 循环改下标就够了。堆这个数据结构的操作本身就集中在“沿着一条路径往下走”天然适合用下标表达用指针反而绕远路。提示如果你在面试里被要求实现堆优先写数组版。指针版不仅写得慢还容易被追问内存占用和缓存效率属于给自己挖坑。1.3 上浮和下滤两个动作千万别用混堆的所有操作最终都归结为两个原子动作上浮sift up也叫 swim和下滤sift down也叫 sink。这两个动作方向相反适用场景也完全不同混用是新手最常见的错误来源。上浮的场景是“元素变大了或者新元素加在末尾”。因为堆的规则是父不大于子如果某个位置的元素突然变大它只可能违反“它不大于父节点”这一条它跟孩子的关系不变因为它变大了只会更满足“父不大于子”所以只需要一路跟父节点比较、必要时交换直到不再违反或者到根为止。典型用法是往堆里插入一个新元素把新元素放在数组末尾然后上浮。下滤的场景是“元素变小了或者堆顶被换掉了”。某个位置的元素变小它跟父节点的关系只会更合规但它可能比自己的孩子还大于是要沿着孩子方向一路往下沉。典型用法有两个删除堆顶把末尾元素搬到堆顶再下滤、以及建堆时对每个非叶子节点做处理。def sift_up(a, i): while i 0: parent (i - 1) // 2 if a[parent] a[i]: break a[parent], a[i] a[i], a[parent] i parent def sift_down(a, i, size): while True: left 2 * i 1 right left 1 smallest i if left size and a[left] a[smallest]: smallest left if right size and a[right] a[smallest]: smallest right if smallest i: return a[i], a[smallest] a[smallest], a[i] i smallest这里有个关键点值得单独强调建堆为什么用下滤而不用上浮从结果上看两种方式都能建出合法的堆但代价不一样。逐个插入加下滤的方式第 i 个元素插入时路径长度是 log i累加起来是 O(n log n)而从最后一个非叶子节点倒着做下滤总代价是 O(n)下一节会把推导写清楚。在堆排序这种对性能敏感的场景这个差别不能忽略。2. 用小根堆做堆排序思路是怎么搭起来的2.1 建堆为什么从最后一个非叶子节点倒着来建堆的代码只有三行但“为什么是 n//2 - 1 开始、为什么倒序”这两个问题能问倒不少人。先说下标。叶子节点没有孩子对它做下滤是空操作纯属浪费。所以要找的起点是“最后一个非叶子节点”。节点 i 是叶子的条件是 2i1 n也就是 i (n-1)/2。反过来最后一个非叶子节点的下标就是 (n-1)/2 向下取整再往下挪一位等价于 n//2 - 1。直接记结论也行但推导一遍更踏实n7 时(7-1)/23节点 3 的孩子是 7 和 8都越界了所以它是叶子节点 2 的孩子是 5 和 6都在范围内所以 2 是最后一个非叶子而 7//2-1 2吻合。再说倒序。下滤这个动作有个前提被下滤的节点的左右子树必须已经是合法的小根堆否则你把根沉下去之后它可能在新位置继续违反规则而你的循环已经结束了结果就是错的。倒着遍历先处理最底层的非叶子它的子树全是叶子天然合法再往上每个节点被处理时它的子树都已经被修好了这个前提就成立了。这就是所谓的“自底向上堆化”。反过来如果从根开始正序下滤会怎样我拿一个具体例子演示过数组[3, 9, 1, 5, 2]。从下标 0 开始3 的左右孩子是 9 和 1最小的是 1交换后变成[1, 9, 3, 5, 2]然后 i 走到下标 2但下标 2 没有孩子循环结束。看结果根 1 是合规的可下标 1 的 9 带着两个孩子 5 和 2两个都比 9 小严重违规。原因就是 9 这棵子树在根下滤之前根本没被修过。所以顺序错了结果就错了。2.2 排序堆顶和末尾交换然后缩小范围建堆完成之后数组的第一个元素就是整个集合里的最小值。堆排序的核心操作就一句话把这个最小值扔到数组末尾去然后让剩下的部分重新变回堆。具体动作是交换 a[0] 和 a[size-1]此时最小值落到了 size-1 这个位置可以认为它已经“排好”了永久不再参与后续的堆操作。交换完之后原来在末尾的那个元素被放到了堆顶它大概率比孩子们大破坏了堆序所以对下标 0 做一次下滤但下滤的范围要限制在 size-1 之内绝对不能让已经排好的尾部元素再被卷进来。这样一轮下来堆的有效范围缩小 1尾部有序区扩大 1。重复这个过程直到堆里只剩一个元素整个数组就有序了。为什么把最小值扔到末尾而不是别的地方因为数组尾部是唯一一个“放进去就不会再动”的位置。如果你把它扔到中间那部分数据还得重新组织就失去了原地排序的意义。这个设计思路跟选择排序有点像都是每轮确定一个最终位置的元素区别在于堆排序用 O(log n) 的下滤取代了 O(n) 的线性扫描来找最小值。这里有个小陷阱值得提前说下滤函数的 size 参数含义是“参与堆化的元素个数”对应下标范围是 0 到 size-1。传参的时候容易传成“最后一个元素的下标”差一位就会把已排好的元素重新搅乱。我建议命名上用size或者heap_len不要用end这种容易歧义的词。2.3 想要升序结果三个办法怎么选这是“小根堆实现堆排序”这道题最坑的地方很多题目要求输出升序但你用的是小根堆跑完出来是降序。这时候有三条路可走取舍不一样。方案做法时间复杂度空间我的评价方案一改用大根堆O(n log n)O(1)最正统但已经不是“小根堆”了方案二小根堆逐个弹出到新数组O(n log n)O(n)逻辑最直观但破坏原地性质方案三小根堆排完降序后反转数组O(n log n) O(n)O(1)最省事多扫一遍代价可忽略我个人的选择是方案三。原因很实在题目既然限定了“用小根堆”那建堆和下滤的比较方向就不该动反转一次数组是 O(n)在 n log n 的主开销面前基本可以忽略而且代码只多两行不容易引入新 bug。方案二在需要“流式输出”或者“只取前 k 个”的场景下是对的但如果只是为了拿到一个排好序的数组白白吃一份 O(n) 的额外内存不划算。至于方案一客观说它才是工程实践里的标准做法——想升序就用大根堆想降序就用小根堆两者代码只差一个比较符号。我在实际项目里从来不会为了“用某个特定堆”而绕路但在刷题、做算法练习的时候刻意练一下“用不顺手的方向实现”对理解比较逻辑的帮助很大。2.4 建堆 O(n) 的推导别只背结论“建堆是 O(n)”这个结论很多人会背但被追问“为什么不是 O(n log n)”就答不上来了。推导本身不难关键是建立一个“高度”的视角。对于一棵有 n 个节点的完全二叉树高度为 h 的节点最多有 n / 2^(h1) 个h 从 0 开始叶子高度为 0。而一个高度为 h 的节点做下滤最多下沉 h 层每层一次比较加可能的一次交换代价正比于 h。于是总代价是总代价 Σ (h 从 0 到 log n) [ h × n / 2^(h1) ] (n/2) × Σ h / 2^h那个级数 Σ h/2^h 从 h1 开始求和结果是 2收敛的。所以总代价约等于 (n/2) × 2 n是线性的。拿 n15 举个具体数字感受一下高度 0 的叶子有 8 个代价 0高度 1 的节点 4 个每个最多下沉 1 层代价 4高度 2 的节点 2 个每个最多下沉 2 层代价 4高度 3 的根 1 个最多下沉 3 层代价 3。合计 11 次操作远小于 n log n ≈ 15 × 4 60。节点越多这个比例差距越明显因为绝大多数节点都在底层它们的下滤路径极短。理解了这一点你就明白为什么“逐个插入建堆”是 O(n log n)那种做法里每个元素都是从叶子位置开始往上走路径长度是它的深度而深度大的节点数量恰恰最多等于把便宜的部分和昂贵的部分搞反了。3. 完整实现从骨架到逐行注释3.1 三个函数撑起全部逻辑不管用什么语言小根堆排序的骨架都是三个部分一个下滤函数、一个建堆循环、一个排序循环。骨架固定之后剩下的全是细节打磨。sift_down(a, i, size) └─ 在 [0, size) 范围内把 a[i] 下沉到合适位置 build_heap(a) └─ for i from n//2 - 1 down to 0: sift_down(a, i, n) heap_sort(a) └─ build_heap(a) for end from n-1 down to 1: swap(a[0], a[end]) sift_down(a, 0, end)下滤函数里最容易出岔子的地方是“三选一”的写法。正确的做法是先假设当前节点 i 是最小的然后依次跟左孩子、右孩子比谁更小就更新最小值的下标最后如果最小值下标还是 i说明已经合规直接返回否则交换并把 i 移动到刚才那个孩子的位置继续下一轮。这里必须注意交换之后 i 要更新成smallest而不是原下标加一或者乘二这个错误我见过不止一次症状是数组只排对了一半。3.2 下滤函数的六个细节一个都不能漏第一个细节边界条件用 size而不是 size。size 表示有效元素个数最大合法下标是 size-1所以判断左孩子是否存在必须写2*i1 size。写成会在数组尾部读到一个已排好的元素把降序结果搞乱。第二个细节右孩子的存在性要先确认左孩子存在。因为完全二叉树的性质决定了不可能出现“有右孩子没左孩子”的情况但代码里如果你先判断右孩子、后判断左孩子逻辑上没问题可读性会变差。我习惯按左、右顺序写。第三个细节比较符号的方向决定堆的类型。小根堆找最小用大根堆找最大用。这一处改掉整个算法的性质就变了所以如果题目要求小根堆这里千万别抄成大根堆的版本。第四个细节提前返回的条件是smallest i不是“没有发生交换”——这两个是等价的但用下标比较更清晰也不容易在后续改动中出错。第五个细节用 while 循环而不是递归。递归版写起来短但深度是 log n虽然不会栈溢出可函数调用开销在百万级数据上能测出差别而且调试时栈帧一层层看很烦。while 版断点只停在一个地方好排查。第六个细节交换用元组赋值Python或临时变量Java不要写a[i] a[smallest]; a[smallest] a[i]这种覆盖式赋值那会把两个元素都变成同一个值。这个错误极其低级但极其常见尤其在手写笔试的时候。3.3 Python 完整实现和测试def sift_down(a, i, size): while True: left 2 * i 1 right left 1 smallest i if left size and a[left] a[smallest]: smallest left if right size and a[right] a[smallest]: smallest right if smallest i: return a[i], a[smallest] a[smallest], a[i] i smallest def build_heap(a): n len(a) for i in range(n // 2 - 1, -1, -1): sift_down(a, i, n) def heap_sort_desc(a): 小根堆原地排序结果为降序 n len(a) if n 2: return a build_heap(a) for end in range(n - 1, 0, -1): a[0], a[end] a[end], a[0] sift_down(a, 0, end) return a def heap_sort_asc(a): 小根堆排序 反转结果为升序 heap_sort_desc(a) a.reverse() return a if __name__ __main__: print(heap_sort_desc([5, 9, 3, 12, 8, 7, 1])) # [12, 9, 8, 7, 5, 3, 1] print(heap_sort_asc([5, 9, 3, 12, 8, 7, 1])) # [1, 3, 5, 7, 8, 9, 12] print(heap_sort_asc([1])) print(heap_sort_asc([])) print(heap_sort_asc([2, 2, 1, 3, 3]))这里n 2的提前返回很重要。虽然不写也不会崩——range(-1, -1, -1)是空序列排序循环range(n-1, 0, -1)在 n1 时也是空的——但显式写出来读代码的人一眼就知道边界被考虑过了。空数组和单元素数组是测试用例里最容易被忽略、也最容易在面试时被追问的两个。跑一遍[5, 9, 3, 12, 8, 7, 1]建堆后得到[1, 8, 3, 12, 9, 7, 5]之后每一轮的过程可以整理成下面这张表方便对照着单步调试。轮次交换后数组下滤后数组尾部有序区1[5, 8, 3, 12, 9, 7, 1][3, 8, 5, 12, 9, 7, 1][1]2[7, 8, 5, 12, 9, 3, 1][5, 8, 7, 12, 9, 3, 1][3, 1]3[9, 8, 7, 12, 5, 3, 1][7, 8, 9, 12, 5, 3, 1][5, 3, 1]4[12, 8, 9, 7, 5, 3, 1][8, 12, 9, 7, 5, 3, 1][7, 5, 3, 1]5[9, 12, 8, 7, 5, 3, 1][9, 12, 8, 7, 5, 3, 1][8, 7, 5, 3, 1]6[12, 9, 8, 7, 5, 3, 1][12, 9, 8, 7, 5, 3, 1]全部第 5 轮交换后堆里只剩[9, 12]两个元素下滤时 9 的左孩子 12 比它大不需要交换所以数组保持不变。第 6 轮堆大小为 1交换后直接结束。整张表能对上说明代码逻辑没问题。3.4 Java 版和 C 标准库的行为差异Java 手写版结构完全一样只是把元组交换换成了临时变量public class MinHeapSort { private static void siftDown(int[] a, int i, int size) { while (true) { int left 2 * i 1; int right left 1; int smallest i; if (left size a[left] a[smallest]) { smallest left; } if (right size a[right] a[smallest]) { smallest right; } if (smallest i) { return; } int tmp a[i]; a[i] a[smallest]; a[smallest] tmp; i smallest; } } public static void heapSortDesc(int[] a) { int n a.length; if (n 2) return; for (int i n / 2 - 1; i 0; i--) { siftDown(a, i, n); } for (int end n - 1; end 0; end--) { int tmp a[0]; a[0] a[end]; a[end] tmp; siftDown(a, 0, end); } } public static void main(String[] args) { int[] a {5, 9, 3, 12, 8, 7, 1}; heapSortDesc(a); System.out.println(java.util.Arrays.toString(a)); } }Java 里有个容易忽略的点数组是引用传递方法内部直接改原数组不需要返回值。很多从 Python 转过来的同学会写成int[] result heapSortDesc(a)然后发现方法签名对不上。另外 Java 自带的PriorityQueue默认就是小根堆想用它做堆排序的话可以反复poll()出来但那样拿到的是升序且需要 O(n) 额外空间跟自己手写的原地版本是两回事。C 这边要特别小心标准库的行为。std::make_heap默认建的是大根堆std::sort_heap也只能把大根堆排成升序。如果你想用小根堆得传比较器std::greaterint()但排出来的结果是降序这两个方向必须记清楚不然面试白板上写完了自己都解释不通。#include algorithm #include functional #include vector int main() { std::vectorint v {5, 9, 3, 12, 8, 7, 1}; std::make_heap(v.begin(), v.end(), std::greaterint()); // 小根堆 std::sort_heap(v.begin(), v.end(), std::greaterint()); // 排完是降序 return 0; }还有个隐藏坑sort_heap要求输入区间已经是合法堆如果忘了先make_heap或者中间对容器做了 push_back堆结构就被破坏了sort_heap的结果没有意义。它不会报错只会给你一个看起来像乱序的东西调试起来特别费劲。语言内置堆工具默认堆类型备注Pythonheapq小根堆只提供函数不封装类JavaPriorityQueue小根堆类封装支持自定义比较器Cpriority_queue / make_heap大根堆两者默认方向不同时需要显式传 greater4. 踩坑实录与排查清单4.1 结果反了、只有一部分有序先查这三处症状一整个数组完全反了。这个最好排查九成是“堆类型和预期结果方向对不上”。小根堆排出来必然是降序如果你要升序却没做反转或者误以为小根堆会给出升序那就是理解偏差不是代码 bug。反过来检查你建堆时用的比较符号是小根堆、是大根堆改回去就对了。症状二前半部分有序、后半部分乱。这种往往是下滤的 size 参数传错了。比如排序循环里把sift_down(a, 0, end)写成了sift_down(a, 0, n)那么每一轮下滤都会把已经扔到末尾的最小值又捞回来堆的有效范围永远不会缩小最后只有堆顶附近看起来是对的尾部一片混乱。还有一种可能是交换后 i 的更新写成了i 2 * i 1跳过了“跟哪个孩子换就往哪走”的逻辑导致元素沉到了错误的子树上。症状三前几个元素对中间开始错但数组元素没丢。这种基本是交换写错了用覆盖式赋值把某个元素吃掉又复制了一份只不过恰好数值相近没看出来。跑一个带重复元素的用例最容易暴露比如[3, 3, 1, 3]如果排序后元素个数对但值不对就是这个问题。4.2 越界和死循环两种情况分开处理越界几乎总是出在2*i1 size这个判断上。少写一个、多写一个、把 size 和 n 搞混都会在数组尾部一拍即合地读到一个不该读的元素。我的习惯是在下滤函数开头加一行断言或者打印跑小数据的时候盯一眼下标范围比事后猜要快得多。死循环的成因比较集中交换之后 i 没有前进。如果smallest算出来等于 i代码应该直接返回但如果判断写成了if smallest i: return那永远是假循环就停不下来了。还有一种隐蔽情况是用做比较遇到相等元素时会把最小值下标更新成孩子交换一次之后两个相等的值互换位置下一轮又换回来来回空转。这不会无限循环因为交换后下标确实前进了但会白白多做一倍的交换性能上能测出来。注意写堆的下滤时比较一旦用了虽然结果正确但相等元素的相对顺序会被反复打乱这是堆排序不稳定的一个直接原因也是它在有稳定性要求的场景里不能用的根源。4.3 为什么我的堆排序比快排慢一大截这个疑问我收到过很多次。按复杂度算堆排序 O(n log n) 和快排 O(n log n) 是一个量级凭什么快排快答案在常数因子里具体是三个原因。第一是缓存不友好。堆排序的访问模式是“从下标 0 跳到下标 1 或 2再跳到下标 3 到 6”跳跃跨度随层数指数增长。数据量一大每次下滤几乎都是一次缓存未命中。快排是顺序扫描加局部交换访存模式友好得多。第二是分支预测。堆排序里“左孩子小还是右孩子小”这个判断结果很不规律CPU 的分支预测器很难猜准每次猜错都要清流水线。第三是交换次数。堆排序的交换发生在相距很远的位置之间快排的交换集中在当前区间内写回代价低。我做过粗略的对比测试在 Python 里对一个百万元素的列表排序heap_sort_desc加上reverse的总耗时大概是内置sorted()的三到六倍具体倍数取决于数据分布和机器。这个数字只是量级参考不是严格 benchmark但足以说明问题库函数用的是经过高度优化的 Timsort手写堆排序在 Python 这种解释型语言里天然吃亏。在 C 或者 Rust 里差距会小一些但趋势一致。对比项堆排序快排归并平均时间O(n log n)O(n log n)O(n log n)最坏时间O(n log n)O(n^2)O(n log n)额外空间O(1)O(log n)O(n)稳定性不稳定不稳定稳定缓存友好度差好中等4.4 常见问题速查表现象最可能的原因排查动作结果整体降序但你要升序小根堆的固有性质反转数组或改用大根堆只有前一半有序下滤的 size 传成了 n检查排序循环里的第三个参数数组元素丢失或重复交换用了覆盖式赋值改用临时变量或元组交换某处越界异常2*i1 size写成打印下标和 size 对照循环不退出交换后 i 未更新检查i smallest这一行建堆后根正确但子树违规建堆用了正序改成从 n//2-1 倒序重复元素排序后数量对但值错比较用了且交换逻辑有误换成再验一遍数据量大时明显变慢常数因子问题非算法错误属正常现象别硬优化5. 从这道题往外延堆在实际场景里的用法5.1 前 K 个最大元素小根堆的经典姿势堆排序本身在工程里出现得不多但“堆”这个结构用得极多最常见的就是 TopK。求一亿个数里最大的 100 个正确做法是维护一个大小为 100 的小根堆遍历每个数堆没满就塞进去堆满了就比较堆顶比堆顶大就替换掉堆顶再下滤比堆顶小就直接丢弃。全部遍历完堆里剩下的就是最大的 100 个。为什么求“最大”反而用小根堆因为堆顶是这 100 个候选里最小的那个它是“守门员”任何比它还小的数都没资格进来一眼就能淘汰。如果用大根堆堆顶是候选里的最大值你没法用它做筛选只能把所有数都存下来再排内存直接爆掉。这个反向思维是 TopK 问题的核心我在面试里问过很多人答不上来的基本都是被“求最大就用大根堆”的直觉带偏了。import heapq def top_k_largest(nums, k): if k 0: return [] heap [] for x in nums: if len(heap) k: heapq.heappush(heap, x) elif x heap[0]: heapq.heapreplace(heap, x) return sorted(heap, reverseTrue)这段代码的时间复杂度是 O(n log k)空间 O(k)。对比全排序的 O(n log n) 和 O(n) 空间在 n 远大于 k 的时候优势非常明显。heapq.heapreplace这个函数值得记住它等价于“弹出堆顶再压入新元素”但只做一次下滤比分开调用heappop和heappush少一半操作。5.2 手写堆还是用库判断标准是什么库函数该用就用但手写的能力不能丢。我的判断标准很简单如果只是需要一个优先队列的语义直接用库如果需要在堆内部做定制操作比如修改某个元素的优先级、删除任意元素、合并两个堆库的封装反而碍事这时候手写更灵活。Python 的heapq只提供函数作用在普通列表上好处是你可以直接操作底层数组坏处是没有封装任何对列表的非法改动都会破坏堆结构。Java 的PriorityQueue封装得比较严想改元素只能先 remove 再 add代价是 O(n)remove(Object)内部是线性查找。C 的priority_queue连迭代器都不给只能看堆顶想做“修改堆中元素”这种操作基本得自己写。需求推荐做法理由单纯取最大/最小用库稳定、省事、常数优化好求 TopK用库的小根堆heapq / PriorityQueue 直接可用需要索引定位元素手写带位置映射的堆库不支持 O(log n) 修改教学、面试白板手写考察的就是过程多路归并用库每路一个元素入堆逻辑简单5.3 堆排序真正合适的场景堆排序在通用排序里确实不占优但它有两个不可替代的特点最坏情况也是 O(n log n)以及额外空间 O(1)。这两条加在一起在内存极度受限、又不能被恶意数据拖慢的场合就有价值。比如嵌入式设备上排序一批传感器数据内存只有几十 KB开不出归并排序需要的辅助数组快排又怕遇到已经有序的输入退化堆排序的确定性就很香。另一个场景是“边生成边排序”。堆天然支持增量操作数据流不断进来你可以在任何时刻取出当前的最小值而不需要等全部数据到齐。这种特性在做任务调度、事件模拟、合并多个有序文件时都用得上。我在一个日志合并的小工具里就用过这个思路多个按时间排好序的日志文件每个文件取第一条放小根堆弹出最早的一条输出再从对应文件补一条进去整个合并过程的内存占用只有文件数量的规模跟日志总量无关。还有一点值得说很多人觉得堆排序“只会出现在教科书里”其实 JDK 里PriorityQueue的底层就是堆Arrays.sort对基本类型用的是双轴快排但对对象数组用的是 Timsort而某些场景下的部分排序比如partialSort背后也是堆的思路。你手写一遍堆排序不是为了以后真的手写它而是为了在读到这些库的实现时能一眼看懂它在干什么。我个人在实际操作中的体会是堆这个结构最值钱的地方不是“排序”而是“用 O(log n) 的代价维护一个动态的最值”。只要你的问题里出现“不断有数据进来我要随时拿到当前最大/最小”就该想堆只要出现“数据量太大我只需要前 k 个”也该想堆。至于排序本身把这道每日一题当成一次刻意练习就好闭卷手写一遍三天后再写一遍然后把比较符号反过来写一遍大根堆版本最后把“降序改升序”的三种方案各实现一次。这一套走下来堆这块基本就不会再忘了。
