面试算法题遇到堆排序很多人第一反应是背模板但真到写代码的时候又容易在heapify的边界条件上卡住。我见过不少工作两三年的开发者能讲清楚堆排序的思路可一上手写shiftDown右孩子的索引判断就会出错。这篇文章就从堆的存储结构讲起把建堆、排序、复杂度推导、常见编码错误、实际应用场景一次性梳理清楚供准备面试的读者和需要在系统中手动实现堆结构的开发者参考。1. 堆排序解决的问题和它不可替代的价值1.1 为什么排序算法已经这么多了还是要学堆排序排序领域有快速排序、归并排序、插入排序工程上几乎都有成熟的库函数调用看起来自己实现堆排序像是重复造轮子。但堆排序有两点是其他主流排序给不了的。第一它是在最坏情况下时间复杂度仍然稳定为 O(n log n) 的原地排序。快速排序平均复杂度很优秀但遇到分布极端的数组时可能退化到 O(n²)。归并排序的复杂度稳定却需要额外 O(n) 的辅助空间。堆排序在这两者之间找到了折中不需要额外空间也不需要担心输入数据分布导致退化。第二我们常用的优先队列、系统定时器、TopK 问题底层几乎都是堆结构。与其说堆排序是一个排序算法不如说它是堆这种数据结构最直接的应用展示。理解堆排序的过程等于同时理解了优先队列的入队出队原理。我之前在某个高并发服务里做热点数据的 TopK 统计数据源源不断进来不可能全存下来再排序。最后的方案就是用一个小顶堆堆顶就是当前第 K 大的候选值新元素来了先跟堆顶比较该替换就替换全程只需要维护 K 个元素的内存。这套思路如果没仔细理解过堆的下沉操作现场写很容易出 bug。1.2 前置知识你需要先搞懂完全二叉树和堆的性质堆本质上是一个数组但这个数组的逻辑结构是一棵完全二叉树。所谓完全二叉树指的是除最后一层外每一层节点都是满的最后一层节点从左到右连续排列中间不能有空缺。数组存完全二叉树有个非常巧妙的好处不需要任何指针或者引用纯靠下标计算就能找到父子关系。对于下标从 0 开始的数组索引为i的节点左孩子下标2 * i 1右孩子下标2 * i 2父节点下标(i - 1) / 2这种存储方式让整个堆可以在一块连续的内存里完成所有操作这也是堆排序能做到原地排序的根本原因。堆还有一个额外约束。大顶堆要求每个父节点的值都大于等于它的两个孩子小顶堆则相反每个父节点都小于等于它的两个孩子。这个约束让我们可以快速拿到整个集合中的最大值大顶堆的根或最小值小顶堆的根并且拿完之后通过一系列下沉操作能在 O(log n) 时间内恢复约束让次大或次小值浮到根节点。2. 建堆为什么必须从最后一个非叶子节点开始2.1 从下往上调整才是线性复杂度堆排序的第一步是建堆。给定一个任意乱序数组我们要把它调整成大顶堆。很多初学者会从上往下逐个节点调整也就是从根节点开始把每个子树位置上的节点都下沉到位。这种做法逻辑上没有错但效率完全不对。正确做法是从最后一个非叶子节点开始往前逐个做下沉调整。最后一个非叶子节点的下标是n / 2 - 1整数除法推导方式很直接最后一个节点的下标是n - 1它的父节点下标为(n - 1 - 1) / 2 n / 2 - 1。为什么从它开始而不是从根节点开始因为我们做下沉调整的前提是该节点的左右子树已经是堆。从最后一个非叶子节点开始它的两个孩子一定是叶子节点叶子节点天然满足堆约束前提成立。自底向上逐个处理等走到根节点时整棵树的每一棵子树都已经满足堆性质根节点就位后整个数组就是大顶堆了。如果反过来从根节点开始下沉根节点左右子树都还不是合法堆下沉完根节点这一层子树内部的乱序问题依然存在后面还要反复重新调整整棵子树复杂度会退化到让人无法接受。手动模拟一个小数组更直观。假设数组为[4, 10, 3, 5, 1]长度n 5最后一个非叶子节点下标是5 / 2 - 1 1也就是值为10的节点。它的左右孩子分别是下标 3 的值 5 和下标 4 的值 110 比两个孩子都大不需要移动。往前走到下标 0值 4左右孩子是值为 10 的节点和值为 3 的节点10 比 4 大交换位置。交换后原本下标 1 的位置现在放着 4它的孩子是下标 3 的 5孩子更大继续下沉。最终得到[10, 5, 3, 4, 1]一个大顶堆成型。2.2 建堆复杂度的直觉与数学推导很多人觉得建堆要对每个节点做下沉每个下沉最坏要走 O(log n) 层那总复杂度应该是 O(n log n)。这个结论对后面每个节点单独插入式地建堆成立但对自底向上建堆的情况就过于保守了。关键在于不同层级的节点下沉的代价是不同的。离根越远的节点数量越多但它们能下沉的路程越短。最后一层有大约 n/2 个叶子节点它们压根不需要调整花费为 0。倒数第二层有大约 n/4 个节点每个最多下沉一层。倒数第三层有大约 n/8 个节点每个最多下沉两层。把这部分开销加起来总工作量符合以下级数S n/4 * 1 n/8 * 2 n/16 * 3 ...这个级数求和会收敛到一个常数倍的 n所以建堆的复杂度是 O(n)而不是 O(n log n)。这里的直觉可以类比成搬家住在高层的住户少但搬运距离远住在低层的住户多但搬运距离近。楼层越高住户越少两头一抵消总时间不会太夸张。3. 排序阶段到底在反复做什么事3.1 堆顶与末尾元素的交换策略建堆完成后数组的索引 0 处是全局最大值。排序阶段的核心操作是把这个最大值跟数组最后一个元素交换让最大值固定到最终位置然后让堆的规模减一对剩下的堆重新调整。这一步为什么能保证正确因为大顶堆的根节点一定是当前堆中的最大值。把最大值放到末尾后最大值就再也不参与后续调整了相当于从堆里摘除了这个节点。剩下的 n-1 个元素里只有根节点换了新内容可能破坏堆约束所以只需要对根节点做一次下沉就能让剩余元素重新成为一个合法的大顶堆新根又会是剩余元素中的最大值。重复这个过程数组末尾就会从后往前依次排列出最大值、次大值、第三大值……还是用刚才的例子。初始大顶堆是[10, 5, 3, 4, 1]堆规模是 5。交换堆顶 10 和末尾 1数组变为[1, 5, 3, 4, 10]把索引 4 的数字 10 排除对前 4 个元素调整。1 下沉到两个孩子值 5 和 3 之间跟较大的5交换位置 1 的 1 再跟孩子 4 比较1 油下沉到位置 3。调整后前 4 个元素变成[5, 4, 3, 1]。接着交换 5 和末尾的 1数组变成[1, 4, 3, 5, 10]再调整前 3 个元素。重复下来最终数组就是从小到大排列[1, 3, 4, 5, 10]。这个过程每轮交换后只需要 O(log n) 的下沉操作一共执行 n-1 轮所以排序阶段复杂度确定是 O(n log n)。加上前面 O(n) 的建堆阶段堆排序的整体时间复杂度就是 O(n log n)。3.2 边界条件是堆规模的隐形控制线排序阶段最容易出错的地方是下沉操作的边界不再是整个数组而是不断缩小的堆规模heapSize。比如数组长度为 10第一轮交换后索引 9 的位置已经放了全局最大值下一轮下沉时如果还按2*i 1 10来判定孩子是否存在就会把末尾已排好的元素重新拉回待调整区域把刚排好的最大值又堆到根节点上去整个排序进程就崩了。正确的写法是每轮交换后heapSize--所有关于孩子是否存在的判断都基于这个不断收缩的heapSize而不是原始的n。我见过不少堆排序的调试案例最终问题都出在这个变量的遗漏上。要么是忘了把heapSize传进shiftDown函数要么是函数内部又隐式地用回了原始长度。这里可以直接背下一套惯例堆排序函数内部维护一个heapSize变量建堆时等于 n每交换一次就减一shiftDown函数统一接收这个变量不再依赖数组的固有长度。这样一来边界判断条件就只剩下一种左孩子下标是否小于heapSize。4. 亲手实现一遍堆排序用代码验证每一个细节4.1 完整 Java 实现与逐行解释下面这段代码我实际跑过多组数据包括随机数组、近乎有序的数组、全等元素数组行为都符合预期。public class HeapSort { public static void heapSort(int[] arr) { if (arr null || arr.length 1) { return; } int n arr.length; // 第一步建立大顶堆 // 从最后一个非叶子节点开始向前逐节点下沉 for (int i n / 2 - 1; i 0; i--) { siftDown(arr, i, n); } // 第二步逐个将堆顶元素交换到末尾 for (int i n - 1; i 0; i--) { // 当前堆顶是剩余元素的最大值 swap(arr, 0, i); // 堆规模缩减为 i重新调整堆顶 siftDown(arr, 0, i); } } /** * 下沉操作将 arr[index] 在大小为 heapSize 的堆中调整到合适位置 * 前提index 的左右子树都已经是合法的堆 */ private static void siftDown(int[] arr, int index, int heapSize) { while (true) { int largest index; int left 2 * index 1; int right 2 * index 2; if (left heapSize arr[left] arr[largest]) { largest left; } if (right heapSize arr[right] arr[largest]) { largest right; } if (largest index) { // 当前节点比孩子节点都大不需要再下沉 break; } swap(arr, index, largest); // 移动到交换后的位置继续向下检查 index largest; } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }重点看siftDown里的largest变量。它不是简单地跟左孩子比较完就交换而是先假设当前节点最大然后依次跟左孩子、右孩子比较选出三者中的最大值下标。这样做的原因是当前节点可能同时小于左右两个孩子需要跟其中更大的那个交换。如果只跟左孩子比忽略了右孩子更大的情况一次下沉结束后堆结构依旧是坏的。交换完成后index largest表示节点移动到了原本那个孩子的下标位置继续循环往更深层调整。整个过程是迭代式的不递归避免了大数组上递归调用栈的开销问题。4.2 一种容易写错的变体用siftUp建堆很多教材还把堆的插入操作叫上浮siftUp意思是新元素放到数组末尾后不断跟父节点比较如果大就往上换。用siftUp也能建堆只要从下标 0 开始逐个把新元素上浮到正确位置。for (int i 0; i n; i) { siftUp(arr, i); }这个写法可以 work但它跟前面说的自底向下沉建堆有本质差别。siftUp相当于模拟了 n 个元素依次插入空堆的过程每次插入的代价是 O(log n)总复杂度是 O(n log n)比自底向下沉的 O(n) 慢一个数量级。我建议初学阶段只练siftDown因为排序阶段只能用下沉建堆阶段用下沉效率最高。两套操作混着写容易把概念搞混。等真正理解了下沉和上浮的区别再回过头看优先队列的插入操作就会很顺。提示如果面试时写堆排序先解释清楚建堆为什么从n/2 - 1开始再动手写代码这是加分项。直接把代码默写出来反而显得没有思考过程。5. 稳定性、空间复杂度与隐藏的坑5.1 堆排序为什么是不稳定排序稳定性指的是排序后相同键值的元素前后相对顺序不变。堆排序在这点上是不达标的。原因非常典型堆排序的交换操作经常跨越很远的距离。比如大顶堆建堆时一个值比较小的元素可能从数组末尾一路下沉到接近头部的位置或者堆顶最大值一下子被换到末尾。当两个相等的元素分布在不同位置时siftDown的交换过程可能让先出现的元素跑到后出现的元素后面去。假设数组中有一个值为 5 的元素在索引 2另一个同为 5 的元素在索引 7。堆调整时第一个 5 可能被交换到更深层第二个 5 反而浮了上来两者的先后顺序就此颠倒。这种跨距离的、跳跃式的交换天生就破坏稳定性。如果业务场景对稳定性有明确要求比如按成绩排序后还要保持同名次学生的学号顺序那堆排序不是好的选择归并排序才是。5.2 空间复杂度与缓存命中率的实际表现堆排序的空间复杂度是 O(1)因为所有交换都在原数组上操作没有申请额外数组。这个特性在内存受限的嵌入式环境或超大数组排序场景里非常宝贵。不过实际运行时间上堆排序通常比快速排序慢。主要原因是快速排序的访问模式对 CPU 缓存很友好——它按分治区域顺序访问每次比较的数据在内存中比较接近而堆排序的下沉操作频繁在数组的远处跳来跳去。比如根节点下沉时可能要访问下标 0、1、2、3、5……这些位置上数据都分散在不同的缓存行里缓存命中率明显下降。对于百万元素以内的常规内存排序快排基本稳压堆排序一头。堆排序真正的用武之地集中在以下几个方向需要严格最坏复杂度保证的实时系统内存极小、没法开额外空间的场景只需要拿到前 K 个最大值而不需要全量的场景数据不断动态插入需要动态维护最值的场景三种主流 O(n log n) 排序的对比如下算法最好复杂度平均复杂度最坏复杂度空间稳定性快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定5.3 现场调试的常见坑位清单按照我个人长时间跟堆排序代码打交道总结出的经验最容易翻车的坑有这几个。第一个坑是siftDown里忘记更新当前检查的下标。用while循环时如果交换条件不满足就直接退出自然没问题但一旦发生了交换代码必须把index更新为largest继续往下否则就变成只交换一次就草草收尾整个堆序完全不对。第二个坑是建堆的起始下标写错。有人会写for (int i n / 2; i 0; i--)从n/2开始。这个位置是纯叶子节点对叶子节点做下沉当然不会报错但它多做了无效工作而且会掩盖对为什么从这里开始的理解面试官追问时很容易露馅。第三个坑是排序循环的边界。写成for (int i n - 1; i 0; i--)这样会把长度为 1 的堆也拿来做一次多余的交换虽然没有致命影响但语义上不干净。标准写法是for (int i n - 1; i 0; i--)。第四个坑是大小顶堆混淆。建好了大顶堆排序阶段把堆顶最大值往末尾放排出来的是升序。如果构建的是小顶堆堆顶是最小值交换后末尾放的是最小值排列出来是降序。想排升序却写了小顶堆的siftDown结果就是一次徹头彻尾的降序错误。不过不会出现元素丢失或重复纯看结果容易被误判成排序成功了。第五个坑比较隐蔽涉及到右孩子的判断。写if (right heapSize arr[right] arr[largest])时优先判断right heapSize别一开始就访问arr[right]。如果heapSize恰好是 2当前节点下标为 0左孩子下标为 1右孩子下标为 2。此时右孩子越界不检查就直接访问会抛出数组越界异常。每次写完堆排序我建议立刻拿几组特殊数据自测空数组、单元素数组、两个逆序元素、全部相同元素、大数组倒序。这些都是堆排序最容易暴露出问题的测试用例。6. 堆排序不只是排序延伸出的经典应用6.1 TopK 问题用大小堆反向思考堆排序中最常被用于实战的不是排序整个数组而是从海量数据里找出最大或最小的 K 个元素。求最大 K 个元素用一个容量为 K 的小顶堆。前 K 个元素直接放进堆之后每来一个新元素如果它比堆顶也就是当前 K 个候选里最小的那个还要大就替换掉堆顶并下沉堆顶会更新为新的第 K 大值。整个数据流走完后堆里剩下的 K 个元素就是整体最大的 K 个。思路里最关键的反直觉点在于想找大的却要维护一个小的堆。因为小顶堆的堆顶是当前范围内最容易被踢出去的门槛任何想挤进 TopK 的元素都要先跨过这个门槛。如果用小顶堆做筛选相当于这个堆始终保留着当前见过元素中最大的 K 个。对应地求最小的 K 个元素就维护一个容量为 K 的大顶堆堆顶是当前候选里最大的那个新元素比堆顶小时替换掉它。这个场景下堆排序的 O(n log n) 全量优势变成了 O(n log K)当 K 远小于 n 时收益非常明显。比如一个亿级数据量的日志系统里要取 Top1000用堆就能把工作规模限制在千级别上内存占用极小。6.2 优先队列和定时器的底层实现优先队列的本质就是堆。Java 里的PriorityQueue、C 的priority_queue、Python 的heapq底层都是堆结构的变体。入队操作对应siftUp出队操作对应把堆顶元素弹出后把末尾元素挪到根节点做siftDown。理解这个底层对日常开发也有帮助。比如用PriorityQueue做任务调度时任务不是先进先出而是按照优先级出队。写一个带时间戳的任务触发器可以把触发时间当优先级时间最小的在堆顶每次只要检查堆顶是否到时间即可复杂度从 O(n) 的线性扫描降成 O(log n)。工业级的定时器实现也大多基于小顶堆。无数个定时事件被组织在一个小顶堆里堆顶永远是下一个最先到期的任务。系统只需要盯着堆顶时间一到就执行并弹出比遍历所有定时器高效得多。我在某个消息推送服务里就用过类似方案。用户自定义推送时间服务启动后把未来一段时间内要推送的任务塞进小顶堆循环线程每隔一段时间检查堆顶时间到达就触发推送然后调整堆。这个实现稳定跑了很久核心代码量不超过一百行。6.3 外部排序中堆的身影当数据量大到内存装不下需要放在硬盘上做排序时通用手法是外部排序。外部排序的基础是多路归并把大文件切分成多个有序的子文件然后像多路归并排序那样在所有子文件的头部元素中找出最小或最大的一个写回结果文件。找所有子文件头部元素中最小值这一步如果线性扫描假设有 M 个子文件每输出一个元素都要比较 M 次代价是 O(M)。换成 M 大小的堆结构每输出一个元素只需 O(log M) 次操作。当子文件数量达到几百甚至几千个这个优化带来的性能提升是很可观的如今常见的数据库排序算法中依然能看到类似思路。外部排序这件事上堆的价值不在于排序速度本身而在于维持当前全局最值的高效性。这跟堆排序的核心思想是同源的堆不保证所有元素有序它只承诺随时能告诉你当前最值并支持快速刷新。最后再分享一个调试小技巧我的习惯是写完全套堆排序代码后用一段带有打印的调试版验证过程每执行一次swap就打印数组当前的顺序和堆的规模。这样可以很直观地看到最大值如何一步步从堆顶挪到末尾和教科书上的示例过程完全对上。等确认逻辑没问题再把打印语句删掉替换成随机数据做批量测试。对工程中真正要使用的代码我个人的经验是优先调用语言标准库的排序函数它们的实现通常是混合了插入排序、快排、堆排序优点的优化版本不比自己写的裸堆排序差。真正需要手写堆的场景是那些只需要维护最值、不需要全排好的地方。搞明白堆排序最大的收获不是多会一种排序写法而是建立起对堆结构的直觉这份直觉在系统设计里能派上大用场。