一提起堆排序（HeapSort），很多人第一反应是：思路我懂，不就是构建一个大顶堆，然后挨个取堆顶吗？可真到要完整写出来的时候，下标错一位、左右孩子越界、排序后半段结果乱了——这些坑我踩过，也帮不少人排查过。这篇就把HeapSort从建堆到排序的每一步掰开，顺便讲清楚它为什么能做到稳定的O(n log n)时间复杂度，却又无法保证排序稳定性。适合刚上手算法的读者，也适合面试前想一口气把手写堆排序练利索的同学。
1. 堆排序核心思路：把“找最大值”这件事做的更快
1.1 排序的本质，其实是反复找最大/最小值
先聊一个看起来很笨的想法：每次从数组里扫一遍找出最大值，放到最后一位，然后忽略它，再扫剩下部分找最大值。每次扫描是O(n)，一共要排n个元素，整体就是O(n²)。这就是选择排序的朴素版本，思路没问题，问题出在“找最大值”这个动作太慢了。
如果有一种数据结构，它能让你在短时间内拿到最大值，同时删除最大值和插入新元素也很快，那么整个排序过程就能大幅提速。这个数据结构，就是二叉堆。堆排序（HeapSort）的本质，就是借助堆这种结构，把“扫描找最大”变成了“堆里取最大”，从而把排序复杂度压到O(n log n)。
堆排序的核心动作可以概括成三步：先原地建堆，然后循环把堆顶最大值放到数组末尾，紧接着缩小堆范围并调整堆。道理很简单，但落地时很多细节容易错。
1.2 二叉堆到底是什么：隐藏在数组里的“完全二叉树”
堆本质上是一棵完全二叉树，但它不需要真的用指针串起来，而是直接存在数组里。因为完全二叉树的节点编号是连续的，给定一个数组下标，就能直接算出它的父节点和左右子节点。
这里约定最常见的从0开始的编号方式：
- 数组下标i对应的节点，其左孩子下标是 2 * i + 1
- 右孩子下标是 2 * i + 2
- 父节点下标是 (i - 1) / 2
最大堆有个性质：每个父节点的值，都大于等于它的子节点。于是根节点就是整个堆的最大值。堆排序用的就是最大堆，按升序输出时每次把堆顶（最大值）换到数组末尾。
1.3 堆排序在排序家族里的位置
先把堆排序和其他几个主流排序摆在一起看，心里会更清楚它在什么时候合适、什么时候不合适。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
堆排序最亮眼的点有两个：一是最坏情况依然能保证O(n log n)，不像快速排序那样可能退化；二是几乎不用额外空间，是真正意义上的原地排序。但它也有明显短板：不稳定，而且由于数组访问跳跃性强，缓存局部性比快速排序差很多。后面我会专门展开这些点。
2. 开始写代码之前：先吃透“下沉”和“上浮”
2.1 下沉（siftDown）：把某个节点放到它该待的位置
下沉是堆排序里最核心的操作。假设某个节点的值比它的子节点小，它就不满足最大堆性质。下沉要做的事情就是：从当前节点开始，不断和较大的子节点比较，如果子节点更大就交换，然后继续向下检查，直到整棵子树都满足堆性质。
很多人把下沉理解成“大的往上走，小的往下掉”，本质上没错。操作里最关键的是要判断左右孩子是否存在。数组子节点下标可能超出堆的边界，所以每轮比较前必须检查 left < n 和 right < n。
我来写一个最简洁的迭代版本，以整型数组为例：
private static void siftDown(int[] arr, int i, int n) { while (true) { int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < n && arr[left] > arr[largest]) { largest = left; } if (right < n && arr[right] > arr[largest]) { largest = right; } if (largest == i) { break; } int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp; i = largest; } }注意这里的n是当前堆的有效大小，不是整个数组长度。在排序过程中，数组尾部已经排好的部分不属于堆，所以n会不断缩小。
2.2 上浮（siftUp）：插入场景下的反向操作
和下沉相反，上浮用在“向堆里插入一个新元素”的场景。新元素先放在数组末尾，然后不断和父节点比较：如果它比父节点大，就和父节点交换，继续向上走。这个过程一直持续到它遇到一个更大的父节点，或者到达根节点。
上浮代码单独看也很简单：
private static void siftUp(int[] arr, int i) { while (i > 0) { int parent = (i - 1) / 2; if (arr[i] <= arr[parent]) { break; } int tmp = arr[i]; arr[i] = arr[parent]; arr[parent] = tmp; i = parent; } }2.3 为什么堆排序里只需要下沉，不需要上浮
这是面试里经常被问到的点。你仔细想：堆排序的过程是“建堆 + 反复取堆顶”。建堆时如果采取自底向上的方式，用的是下沉；排序阶段把堆顶换到末尾后，新堆顶变成原来末尾的小元素，又需要把它下沉到合适位置。整个排序过程从头到尾没有插入新节点，所以完全不涉及上浮。
上浮真正发挥作用的地方是优先队列的插入操作。如果你想在普通数组上通过不断插入来建堆，那就是另一种复杂度了。这点下面讲建堆时会再说到。
3. 完整实现堆排序：从建堆到排序循环
3.1 原地建堆：为什么从最后一个非叶子节点开始
建堆有两种思路。第一种是模拟插入：从空堆开始，一个个调用上浮，把数组元素加进去，这种建堆复杂度是O(n log n)。第二种是原地自底向上调整：数组本来就是一棵完全二叉树，只是不满足堆性质。我们从最后一个非叶子节点开始，往前一个一个做下沉，就能把所有子树调整成合法堆。这种建堆方式的复杂度只有O(n)。
最后一个非叶子节点的下标是多少？对于长度为n的数组，最后一个叶子节点是 n - 1，它的父节点是 (n - 1 - 1) / 2，也就是 n / 2 - 1。从它开始往前遍历到0即可。叶子节点本身没有子节点，天然就是合法堆，不需要下沉。
建堆代码：
int n = arr.length; for (int i = n / 2 - 1; i >= 0; i--) { siftDown(arr, i, n); }为什么自底向上建堆是O(n)而不是O(n log n)？因为越靠近叶子的节点，下沉时能走的路径越短。最底层的大量节点只需要比较一次甚至不用比较，只有靠近根部的少数节点才需要下沉较深。把所有节点下沉高度加起来，是一个等差级数，算出来是线性的。具体推导不在这里展开，但你只要记住结论就好：不是所有节点都做O(log n)次操作，整体上建堆是O(n)。
3.2 排序循环：堆顶和末尾交换，然后缩小堆范围
建好最大堆之后，数组的第一个元素就是整体最大值。此时把堆顶和当前堆的最后一个元素交换，这个最大值就放在数组末尾了。接下来让堆的大小减一（因为末尾已经排好，不该再参与堆调整），再从新堆顶开始下沉，恢复最大堆性质。重复这个过程，直到堆里只剩一个元素，整个数组就是升序了。
完整排序循环：
for (int i = n - 1; i > 0; i--) { int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; siftDown(arr, 0, i); }写这个循环时最容易犯的错误是：siftDown的第三个参数直接写成了n，而不是当前的堆大小i。如果写n，已经放到末尾的最大值会被重新加入堆，排序结果直接乱掉。这个坑我在专门一章节里会再强调。
3.3 一个完整的排序过程模拟
拿一个具体数组走一遍，比空谈理论有用得多。现在有数组 [4, 10, 3, 5, 1]，我们模拟一下完整堆排序。
先建堆，n = 5，最后一个非叶子下标是 5 / 2 - 1 = 1。
- i = 1，节点值是10，左孩子下标3值是5，右孩子下标4值是1。10比两个子节点都大，不需要移动。
- i = 0，节点值是4，左孩子下标1值是10，右孩子下标2值是3。最大的是左孩子10，交换后数组变成 [10, 4, 3, 5, 1]。
- 下沉还没结束：当前节点在i = 1，值是4，左孩子下标3值是5，右孩子下标4值是1。5更大，交换后数组变成 [10, 5, 3, 4, 1]。
现在最大堆建好了，根节点是10。
开始排序循环：
- i = 4：交换arr[0]和arr[4]，数组变成 [1, 5, 3, 4, 10]。堆大小变成4，对堆顶下标0执行下沉。节点1的左孩子5更大，交换得到 [5, 1, 3, 4, 10]；继续下沉i = 1，节点1的左孩子下标3值是4（下标4超出堆大小4，不算），交换得到 [5, 4, 3, 1, 10]。
- i = 3：交换arr[0]和arr[3]，数组变成 [1, 4, 3, 5, 10]，堆大小3。下沉堆顶：节点1，左孩子4更大，交换后 [4, 1, 3, 5, 10]。
- i = 2：交换arr[0]和arr[2]，数组变成 [3, 1, 4, 5, 10]，堆大小2。下沉堆顶：节点3，左孩子1（下标1）在堆内，但3大于1，不动。
- i = 1：交换arr[0]和arr[1]，数组变成 [1, 3, 4, 5, 10]，堆大小1，结束。
最终结果是 [1, 3, 4, 5, 10]，排序完成。整个过程里，siftDown每次处理的都是当前堆的有效边界i，这是最需要盯住的地方。
4. 复杂度与稳定性：堆排序的得与失
4.1 时间复杂度为什么是稳定的O(n log n)
堆排序的时间复杂度由两部分组成：建堆O(n)，排序循环n - 1次，每次从堆顶下沉最多走O(log n)层，所以排序部分是O(n log n)。两者相加，取大的那个，整体就是O(n log n)。
这里的关键在于：不管输入数组本来就接近有序，还是完全乱序，堆排序都不会受到初始状态影响。最大堆的构建不会因为数据基本有序而更快，排序循环的交换次数也固定。所以堆排序的最好、平均、最坏时间复杂度都是O(n log n)，这在比较类排序里是很难得的稳定性。
代价是常数系数偏高。下沉操作要频繁比较左右孩子、做交换，数组访问的跨度大，对CPU缓存不友好。实际测试里，同样的数据量，堆排序通常明显慢于快速排序。如果你只是给普通数组排序，主流语言内置的排序函数几乎都优于手写堆排序。
4.2 空间复杂度：原地排序到底是怎么做到O(1)的
堆排序在数组自身范围内操作，除了几个临时变量之外，不需要额外的数据结构。所以数据辅助空间是O(1)。这也是堆排序相比归并排序的最大优势：归并排序再怎么优化，也需要O(n)的额外空间来合并两个有序段。
需要注意一个细节：如果siftDown用递归写法，递归调用栈在极端情况下会带来O(log n)的函数栈空间。虽然这不是数据规模意义上的额外空间，但如果你被面试官严格追问“是否真正O(1)”，最好回答“迭代式下沉可以做到严格O(1)辅助空间”。这也是我推荐用迭代而不是递归的原因之一。
4.3 为什么堆排序不稳定
稳定性的定义是：如果有两个相等的元素，排序后它们的相对顺序不能改变。堆排序做不到这一点。
看一个最简单例子。数组 [5a, 5b, 3]，两个5用a和b区分原来先后顺序。建堆后仍然是 [5a, 5b, 3]（因为5a不小于5b，不需要交换）。然后进入排序循环：交换堆顶5a和末尾3，数组变成 [3, 5b, 5a]，堆大小变成2。接着下沉下标0的3：左孩子是5b，5b比3大，交换后数组变成 [5b, 3, 5a]。再交换堆顶5b和当前位置元素3，最终得到 [3, 5b, 5a]。
原来的顺序是5a在5b前，结果5b在5a前，相对顺序被改变了。原因在于：堆排序的交换往往发生在相隔很远的节点之间，堆顶元素会被直接甩到数组尾部，这可能绕过了其他相等的元素。快速排序也有类似的跨距离交换问题，所以同样不稳定。
4.4 和其他排序怎么取舍
实际工作中，我不会单纯因为堆排序复杂度好看就优先选它。排序不是只看时间复杂度，还要看数据规模、稳定性要求、内存限制、甚至数据是否能一次性放进内存。
- 如果要求稳定排序，直接选归并排序或其变体，比如语言内置的稳定排序。
- 如果内存很紧张，且不要求稳定，堆排序可以考虑。
- 如果数据量很大但不需要绝对稳定，快速排序在实际运行时通常最快，绝大多数系统的内置排序也会优先照顾快排、插入排序混合策略。
- 如果需要在动态数据流里反复取最大/最小值，堆不是“排序方案”，而是唯一合适的数据结构，这属于堆的真正主场。
5. 实际写堆排序时的常见坑和排查方法
5.1 下标从0开始还是从1开始，最容易混
很多教材讲堆时喜欢把下标从1开始，因为这样左孩子是2i，右孩子是2i + 1，父节点是i / 2，非常对称。但绝大多数编程语言的数组下标从0开始，如果你硬套下标1的公式，最后一个非叶子节点、左右孩子的计算都会出问题。
从0开始的公式一定要记熟：
- 左孩子：2 * i + 1
- 右孩子：2 * i + 2
- 父节点：(i - 1) / 2
- 最后一个非叶子节点：n / 2 - 1
如果你实在不放心，就自己画一棵完全二叉树，把下标标上去。画一次就知道为什么是这些公式了。
5.2 左右孩子越界判定，是最大的隐性坑
写siftDown的时候，left和right可能在数组范围之外。常见错误是只判断left不判断right，或者在判断里用了 <= 而不是 <。
比如堆大小是n，节点i是最后一个非叶子节点，它的左孩子可能恰好是n - 1，右孩子是n。此时right == n已经不合法。判断条件应该是 left < n，right < n，而不是 right <= n - 1。用 < n 更直观，也避免下标n访问越界。
还有一点：如果left已经越界，说明当前节点是叶子节点，下沉直接结束。如果left在界内但right越界，只需要比较left和当前节点即可。这两个分支都要处理干净。
5.3 排序循环的堆大小，千万别写成整个数组长度
我再三强调这个错误，因为它太容易发生了。建堆阶段下沉用的边界是n，排序阶段下沉用的边界却应该是当前堆大小i。
错误写法：
for (int i = n - 1; i > 0; i--) { swap(arr, 0, i); siftDown(arr, 0, n); // 错！应该用 i }这样做的后果是：每次把最大值放到末尾后，下一次下沉又把末尾的最大值包了进来，等于白干，甚至会把排好的元素重新挪回去。我见过有人调试很久，最后发现就是这里多传了一个n。建议把siftDown的第三个参数命名为heapSize，时刻提醒自己传的是堆大小。
5.4 下沉用递归还是迭代
递归版siftDown写起来可读性不错：
private static void siftDownRecursive(int[] arr, int i, int n) { int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp; siftDownRecursive(arr, largest, n); } }逻辑没问题，但每下沉一层多一次函数调用，数据量大时调用栈有一定开销。迭代版并不难，按我前面给出的while写法就能完全替代。工程上建议用迭代，面试中也更稳妥，因为你还能顺带解释“这样空间复杂度才严格O(1)”。
5.5 “结果不对”时的速查清单
如果排序结果不对，按下面顺序逐项检查，90%的问题能快速定位：
| 症状 | 检查点 |
|---|---|
| 排序结果末尾有几个反序大值 | 排序循环siftDown边界是否写成n |
| 下标越界异常 | 孩子节点判断是否有left < n和right < n |
| 建堆后堆顶不是最大值 | 最后一个非叶子节点起点是否写对 |
| 数组基本有序但结果仍然错 | 是否把建堆和排序循环顺序写反了 |
| 结果递减而不是递增 | 是否建成了最小堆或排序方向搞反 |
还有一个自查技巧：如果是在刷题网站上报错，先小规模打印数组，用3到5个元素手推一遍。堆排序只有几十行代码，人肉模拟一遍非常快。
6. 堆排序之外：堆思想更常见的应用
6.1 TopK问题：找最大的K个数，堆比排序更好用
堆排序最实用的延伸其实是TopK问题。比如给你一个海量数据流，随时想知道到目前为止最大的10个数，你不会把所有数据排序后再取前10，而是维护一个大小为10的最小堆。
过程是这样的：堆里存当前最大的10个数，堆顶是这10个数里最小的那个。新来一个数，如果比堆顶还小，直接忽略；如果比堆顶大，就把堆顶替换成新数，然后执行一次下沉。这样不管数据流多大，内存只需要K个元素，时间消耗是O(n log K)。数据量特别大、内存装不下时，这个方案几乎是唯一可行的。
这和堆排序的思路正好相反：堆排序把整个数组建成堆再逐个取出最大值，TopK则固定堆的大小K，只关心有多少数据比堆里的最小值大。面试中聊到堆，很大概率会扯到这道题。
6.2 优先队列：堆最通常的日常形态
很多语言的标准库里都有优先队列，底层实现就是一个二叉堆。比如Java里的PriorityQueue默认是最小堆，每次出队取最小元素；可以用自定义比较器改成最大堆。C++里的priority_queue则是默认最大堆。这些容器在任务调度、Dijkstra最短路、事件驱动模拟里都被广泛使用。
如果自己手写优先队列，核心就是siftUp和siftDown两个操作。插入元素时先放在数组末尾再上浮，取出堆顶时把末尾元素移到堆顶再下沉。这套逻辑和堆排序里的下沉完全共享，只是多了上浮。理解了堆排序，再去看优先队列源码会非常轻松。
6.3 外部排序与多路归并：堆是幕后功臣
当数据大到内存装不下，外部排序会把数据分块排序成多个有序段，然后再把所有这些有序段合并成一个完整有序的大文件。多路归并时，要从每个有序段当前指针指向的元素里选出最小的一个，这正好可以用一个大小为路数K的最小堆来做。
每次从堆顶取出当前最小元素，写入输出文件，然后从对应路段读取下一个元素，再插入堆并调整。K比较大时，用堆比逐个比较所有路段的当前值快一个数量级。许多数据库和文件排序工具的底层都离不开这个思路。
6.4 从堆排序延伸出的优化思考
堆排序本身在这个时代已经不是排序首选，但围绕堆的思想还有很多优化方向。比如索引堆：在堆节点里额外存一份原始数组的下标，这样在更新任意元素时能快速定位到堆中的位置，适合图中边的动态更新。又比如带权优先队列用在仿真系统里，需要支持删除和更新任意元素，直接用普通二叉堆会复杂不少，但掌握下沉上浮后都能理解。
我个人实际做项目时的体会是：堆排序作为“排序算法”的价值反而没那么大，真正好用的是堆这种数据结构。如果你正在准备算法面试，与其背堆排序的完整代码，不如先把siftDown和siftUp写到条件反射，然后把TopK、优先队列、合并K个有序链表这类题练熟。等你对堆的调整过程足够熟练，再回头看堆排序，会发现它只是“建堆 + 取顶下沉”的组合，自然就写得又快又准了。
