企业官网建设流程全解析

排序算法里，堆排序（Heap Sort）是个很特别的存在。它不像冒泡排序、插入排序那样肉眼可见地直观，也没有快排那种“平均很快但最坏看运气”的随机性；它属于“选择排序的进化版”，每一次都从待排序部分稳稳地挑出最大值，而且不用借助额外数组。真正做到：最好、最坏、平均都是 O(n log n)，原地排序，空间 O(1)。

这篇文章我会把堆排序从上到下拆开讲清楚：先讲堆是什么、为什么能用数组存一棵“看不见指针”的完全二叉树；再讲建堆和排序两个阶段里每个关键步骤的数学依据；然后给出可以直接运行的 Java 实现，逐段解释设计意图；最后把我自己踩过的边界条件、公式记错、稳定性误解这些坑全部列出来。适合刚学完基础排序、想真正吃透堆排序原理并动手写代码的同学。

1. 堆排序在排序家族里的定位：为什么值得认真学

1.1 稳定 O(n log n) 与原地排序的“反差组合”

很多人第一次接触堆排序时，心里会有个疑问：它到底比快排好在哪？我把三种主流排序的契约摆出来你就明白了：

快排的平均表现很好，但最坏情况会退化到 O(n²)，虽然随机化选基准可以缓解，但“最坏有界”这件事在实时系统、嵌入式环境、任务调度里是硬需求。归并排序稳定但是要额外 O(n) 内存，数据量大时内存压力不小。堆排序恰好站在两者中间：不管输入是什么分布，它都严格走 O(n log n)，也不开额外数组。这种“确定性强”的特质，是它一直被保留在教科书和工程工具库里的核心原因。

1.2 堆排序思想延伸出的高频场景

直接拿堆排序来给整个大数组排序的场景，现代工程里其实不算多，因为 JDK 的Arrays.sort对基本类型用的是改良版快排，对对象数组用的是 TimSort，都已经做得很极致。但堆这个结构本身出现的频率非常高：任务调度器里的优先队列、请求超时管理的最小堆、TopK 问题、Dijkstra 最短路径算法、流式数据求中位数，全都建立在“上浮/下沉”这套堆操作之上。

也就是说，堆排序是你理解堆这个数据结构的入口。把堆排序里的siftDown写熟了，后面看PriorityQueue源码、看定时器实现、看各种海量数据筛选场景，全都是同一个思路在复用。这也是我建议每个学算法的人不要跳过堆排序的原因：它不是“过时的排序”，而是一整套数据结构思想的敲门砖。

2. 堆的数据结构基础：完全二叉树与数组的映射

2.1 数组下标背后的父子关系

堆在逻辑上是一棵完全二叉树，物理上却只用一个一维数组存储。所谓完全二叉树，就是除了最后一层外每一层都被填满，最后一层的节点从左到右连续排列。

这种树形结构天然适合数组：按层序遍历的顺序，把所有节点依次放进数组下标 0、1、2、3...，父子关系就直接用下标算出来：

• 左子节点下标：2 * i + 1
• 右子节点下标：2 * i + 2
• 父节点下标：(i - 1) / 2

这组公式是整个堆排序的地基。我见过不少人把左子节点写成2 * i，那是下标从 1 开始的写法，Java 数组从 0 开始，差一个偏移量，代码就会访问到错误的位置。你可以做个简单的验证：根节点下标是 0，它的左子节点应该是 1，套2 * 0 + 1是对的，但2 * 0是 0，指向自己，明显不对。

2.2 大顶堆与小顶堆：排序方向由堆序决定

堆在满足完全二叉树结构之外，还要求一个“堆序性质”：大顶堆要求每个父节点的值不小于它的两个子节点；小顶堆要求每个父节点的值不大于它的两个子节点。注意，堆序只约束父子和祖孙关系，不约束兄弟节点之间的大小，也不保证整棵树像二叉搜索树那样有序。

这个特点很重要，它决定了堆的核心操作：如果某个节点的值比父节点大（在小顶堆里是比父节点小），就往上浮；如果某个节点的值比某个子节点小（在小顶堆里是比子节点大），就往下沉。堆排序里主要用到下沉，也就是siftDown，因为建堆和排序阶段都是父节点不满足堆序往下调整。

2.3 用生活例子理解“堆序”的局部性

打个比方：公司里几乎每个部门经理的工资都高于本部门员工，但不同部门的员工之间工资可以随意高低。这就是堆序的局部保证——只保证上下级关系，不保证横向关系。

这个特性让堆能在 O(1) 时间内拿出全局最值：大顶堆的根节点就是最大值，小顶堆的根节点就是最小值。堆排序正是利用这一点，每次都从堆顶拿走全局最值，再通过下沉把剩余部分重新整理成合法堆，循环往复，就完成了排序。整个过程中，数组内部做交换，不需要额外容器。

3. 建堆过程图解：从最后一个非叶子节点开始

3.1 为什么倒数第二层是调整的起点

建堆的目标是把一个无序数组整理成满足堆序的数组。最朴素的办法是从根节点开始逐个处理，但这里有个关键逻辑：要保证父节点大于子节点，得先保证子节点所在的子树已经不是乱序。换句话说，调整过程必须是“从下往上”的。

叶子节点没有子节点，天然满足堆序，不用调整。第一个需要调整的节点，是最后一个非叶子节点。根据完全二叉树的性质，最后一个非叶子节点的下标是n / 2 - 1。比如数组长度 7，7 / 2 - 1 = 2，也就是说从下标 2 开始往前调整。这个公式很多人记不住，其实推导很简单：最后一个节点的下标是n - 1，它的父节点是((n - 1) - 1) / 2，化简就是n / 2 - 1。

建堆的流程是：从n / 2 - 1开始，往前遍历到 0，对每个节点执行下沉操作，确保以它为根的子树成为合法堆。从后往前的顺序保证了当我们处理上层节点时，下面的子树已经是合法的，这时只需要把当前节点一路“沉”到正确的位置。

3.2 手动模拟一次完整建堆

用数组[4, 10, 3, 5, 1, 7, 6]走一遍建堆过程，数组长度 7，最后一个非叶子节点下标是 2，也就是值为 3 的节点。

第一步，调整下标 2（值为 3）：它的左子节点是下标 5（值为 7），右子节点是下标 6（值为 6），子节点中最大值是 7，大于 3，所以交换 3 和 7。数组变成[4, 10, 7, 5, 1, 3, 6]，当前节点已经下沉到下标 5，没有子节点，结束。

第二步，调整下标 1（值为 10）：左右子节点分别是下标 3（值为 5）和下标 4（值为 1），都小于 10，不需要调整。

第三步，调整下标 0（值为 4）：左子节点下标 1（值为 10），右子节点下标 2（值为 7），最大的是 10，交换 4 和 10。数组变成[10, 4, 7, 5, 1, 3, 6]。但这还没结束，4 现在到了下标 1，它的左子节点下标 3（值为 5）和右子节点下标 4（值为 1）中，5 大于 4，所以继续交换 4 和 5，数组变成[10, 5, 7, 4, 1, 3, 6]。到这里，整个数组已经满足大顶堆性质，根节点是最大值 10。

这整个过程就是siftDown的完整工作方式：一次下沉可能不止交换一步，要一路沉到满足堆序为止。

3.3 建堆复杂度为什么是 O(n)

这是堆排序里最反直觉的一个结论。直观想，每个节点下沉一次是 O(log n)，n 个节点就是 O(n log n)，但建堆整体只有 O(n)。原因是：大多数节点本身就处在比较低的位置，下沉路径很短。

从高度角度算：高度为 h 的节点，下沉最多 h 次。而高度越高的节点数量越少，高度为 h 的节点大约有n / 2^(h+1)个。总工作量是sum(h * n / 2^(h+1))，这个级数收敛，最终结果是 O(n)。换句话说，底层的大量叶子节点根本不用动，高层节点数量少、下沉总次数有限。这个数学结论也解释了为什么建堆比一个个插入建堆更高效——后者是严格 O(n log n)。

4. 排序阶段解剖：交换、缩堆、再下沉

4.1 堆排序主循环的“三步走”

建堆完成后，数组满足大顶堆性质，根节点就是全局最大值。排序阶段的思想非常直接：把最大值放到数组末尾，然后缩小堆的范围，再让新的根节点下沉，重新整理出一个大顶堆，继续取下一个最大值。

具体来说，主循环从i = n - 1开始，一直循环到i = 1：

1. 交换arr[0]和arr[i]，把当前堆的最大值放到数组末尾；
2. 把堆的有效长度heapSize减 1，末尾元素不再参与后续调整；
3. 对新的根节点执行下沉操作，恢复大顶堆性质。

为什么升序排序要用大顶堆？因为升序结果是从小到大排列，最大值必须放在数组末端。把堆顶这个“全局最大”直接换到末尾，正好落位。如果用小顶堆，堆顶是全局最小，换到末尾得到的是降序结果。所以“大顶堆升序、小顶堆降序”不是死记的规则，而是由“把最值换到末尾”这个动作自然决定的。

4.2 手动走一遍关键排序轮次

继续用建堆完成的数组[10, 5, 7, 4, 1, 3, 6]，heapSize 是 7。

第一轮，i = 6：交换堆顶 10 和arr[6]的 6，数组变成[6, 5, 7, 4, 1, 3, 10]，此时 10 已经到最终位置。heapSize 变成 6，对根节点 6 做下沉：它的左右子节点是 5 和 7，最大是 7，交换 6 和 7，数组变成[7, 5, 6, 4, 1, 3, 10]；继续检查 6 的孩子，下标 5 的值是 3，下标 6 已经不在堆范围内，6 大于 3，下沉结束。现在[7, 5, 6, 4, 1, 3]又是合法大顶堆。

第二轮，i = 5：交换堆顶 7 和arr[5]的 3，数组变成[3, 5, 6, 4, 1, 7, 10]。heapSize 变成 5，对根节点 3 做下沉：左右子节点是 5 和 6，最大是子节点 6，交换 3 和 6，得到[6, 5, 3, 4, 1, 7, 10]；继续检查 3 的下标 2，它的左子节点下标 5 已不在堆范围，结束。堆范围变成[6, 5, 3, 4, 1]。

之后每轮都是同样的节奏：拿走堆顶最大值，末尾元素上位，下沉恢复堆序。整个过程走完，数组自然是递增的。从手动模拟可以看到，每次交换后的“下沉”并不保证只下沉一层，而是可能连续交换多次，这就是siftDown被称为“向下渗透”的原因。

4.3 排序阶段最容易写错的一个边界

排序循环里的下沉，边界条件必须是当前的heapSize，而不是整个数组的length。原因很直接：堆的有效范围在每次交换后都在缩小，数组末尾那些已经排好序的最大值，不应该再参与堆调整。如果把边界写成arr.length，那些已经被“隔离”的末尾元素又会被换回堆顶附近，排序顺序直接被打乱。

我在初学阶段就在这里翻过车。逻辑上觉得“反正都要比较，多比较几个也没事”，结果输出结果前面是对的，后面就乱了。排查了很久，发现问题出在siftDown里判断子节点是否越界时写成了arr.length。这是个非常隐蔽的 bug，因为数组长度足够大时，通常只会多调整几个元素，小数据量下顺序看着还像那么回事，数据一多就原形毕露。

5. 可直接落地的 Java 实现与逐行说明

5.1 完整代码：递归版 siftDown 更易理解

下面是一个标准的大顶堆升序排序实现，核心方法就三个：heapSort负责调度，siftDown负责下沉，swap负责交换。

public class HeapSort { public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { 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); siftDown(arr, 0, i); } } private static void siftDown(int[] arr, int i, int heapSize) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < heapSize && arr[left] > arr[largest]) { largest = left; } if (right < heapSize && arr[right] > arr[largest]) { largest = right; } if (largest != i) { swap(arr, i, largest); // 交换后，largest 位置上需要继续检查子树 siftDown(arr, largest, heapSize); } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }

这段代码的通用性没问题，兼容空数组和单元素数组，不需要额外判断。siftDown里先假设当前节点是最大值，然后分别与左右子节点比较，更新最大值的下标；如果最大值不是当前节点，说明需要交换，交换后继续在子树里向下递归检查。

5.2 循环版 siftDown：省掉递归栈的工程写法

递归版本逻辑清晰，适合学习和手写。工程上我更喜欢用循环版，省掉递归栈空间，也让代码行为更可控——虽然堆排序的下沉深度最多是 O(log n)，递归栈开销不大，但在资源敏感的场景里，能少一点是一点。循环版的写法如下：

private static void siftDown(int[] arr, int i, int heapSize) { while (true) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < heapSize && arr[left] > arr[largest]) { largest = left; } if (right < heapSize && arr[right] > arr[largest]) { largest = right; } if (largest == i) { break; } swap(arr, i, largest); i = largest; } }

循环版的核心思想是：每次把i移动到largest的位置，继续下一轮比较，直到当前节点不小于所有子节点。这两种实现做同样的事，选哪种都可以。我建议初学时先写递归版，因为逻辑一目了然；等理解了下沉的本质，再改成循环版，顺便感受一下两者在栈使用上的区别。

5.3 从循环不变量角度检查代码

写算法时有个概念叫“循环不变量”——每一轮循环开始之前，某些条件始终成立。检查堆排序的代码，可以靠这个思路快速验证自己写的对不对：

• 建堆完成后，整个数组[0, n)满足大顶堆性质；
• 排序的每一轮开始前，[0, heapSize)满足大顶堆性质，[heapSize, n)已经按升序排好；
• 交换堆顶和堆尾后，堆顶变成了一个可能偏小的值，但除了根节点，它的左右子树依然满足堆序，所以只需要对根节点做一次下沉，就能让[0, heapSize - 1)重新成为大顶堆。

这个视角特别有用。排查 bug 时，如果发现排序结果不对，先问自己：交换之后，下沉过程是否真的覆盖了所有可能不满足堆序的节点？处理边界时，heapSize传的是不是当前堆有效长度？用循环不变量一层层推理，比盯着输出看半天高效得多。

6. 复杂度、稳定性与性能实测

6.1 时间与空间复杂度拆解

堆排序的总复杂度由两部分组成：建堆 O(n)，加上排序阶段 n-1 次“交换加下沉”，每次下沉 O(log n)，所以总时间是 O(n log n)。由于建堆和排序都不依赖输入数据的初始顺序，最好、平均、最坏三种情况都是 O(n log n)。

空间复杂度上，数组是原地调整，不需要额外存储。递归版siftDown会有 O(log n) 的递归栈，如果严格按“原地”定义，循环版更符合 O(1) 额外空间的标准。这也是我之前建议工程中用循环版的原因之一。

6.2 不稳定的本质原因

堆排序是不稳定的。稳定性指的是排序后相等元素的相对顺序能保持不变。堆排序里，相等元素之间可能出现“跨越式”交换，导致相对顺序改变。

举个例子，数组[5a, 5b, 3]，两个 5 分别用 a 和 b 标记。建堆时先调整下标 1（5b），它大于 3，不需要动；调整下标 0（5a）时，左子节点是 5b，右子节点是 3，最大值的判断取左子节点，5a 和 5b 相等，比较逻辑里arr[left] > arr[largest]为假，所以 5a 不下沉。这个例子恰好没改变相对顺序。换个结构更复杂的数组，堆调整过程中的交换就会让相同元素“越过”彼此，相对顺序就无法保证了。所以不要试图在需要稳定排序的场景里用堆排序，比如按时间戳排序的用户记录，一旦相等元素的顺序被打乱，结果就不可靠。

6.3 实测中的几点直观感受

我在本地用随机数据对比过堆排序和 JDK 的Arrays.sort：对几十万量级的随机整数，堆排序明显比Arrays.sort慢，差不多是 2 到 3 倍的耗时差距。主要原因是Arrays.sort对基本类型用的是双轴快排，对 CPU 缓存非常友好；而堆排序的访问模式是“跳跃式”的，频繁在数组的不同位置之间跳转，缓存命中率不高。

但数据量小的时候，比如几千个元素，两者差距几乎可以忽略。堆排序的强项从来不是“跑得最快”，而是“不管什么数据都稳定在一个量级”。如果业务场景要求排序耗时可控、不能接受最坏情况的劣化，堆排序就是比快排更稳妥的选择。

7. 高频踩坑点与排查速查表

7.1 父子下标公式不可记错

数组从 0 开始，父节点下标是(i - 1) / 2，左子节点是2 * i + 1，右子节点是2 * i + 2。如果从 1 开始，公式是left = 2 * i，right = 2 * i + 1，parent = i / 2，这两种写法不能混用。Java 数组下标天然从 0 开始，所以我统一用第一套公式。记住左子节点加 1，右子节点加 2，就不容易错。

7.2 下沉边界必须用 heapSize

这是我在“4.3 排序阶段最容易写错的一个边界”里强调过的点。在排序阶段，每次下沉都会传入当前堆的有效长度，判断子节点是否存在时必须用这个长度，不能拿arr.length顶替。一个有效的检查习惯是：在siftDown里先打印heapSize，再打印left和right，看看有没有出现越界的情况。

7.3 关于“大顶堆升序、小顶堆降序”的误解

有些同学会想：升序是“小的在前”，是不是应该用小顶堆？这是最常见的误区。堆排序排序阶段的逻辑是把堆顶元素换到数组末尾，所以升序排序时堆顶必须是剩余部分的最大值，也就是大顶堆。小顶堆的堆顶是最小值，换到末尾得到的是降序。如果想通过堆排序得到降序结果，可以建小顶堆，也可以在升序排序完成后把数组反转。

7.4 常见问题速查表

8. 堆排序的延伸应用：TopK、PriorityQueue 与选型建议

8.1 用堆解决 TopK 问题的标准做法

堆排序的高频应用是 TopK：从海量数据里找出最大或最小的 K 个。求最大的 K 个，维护一个大小为 K 的小顶堆；遍历数据时，如果当前元素比堆顶大，就替换堆顶并下沉，这样堆里始终保留着“目前见过最大的 K 个”，堆顶则是这 K 个中的最小值。遍历完，堆里的 K 个元素就是全局最大的 K 个。复杂度是 O(n log K)，K 远小于 n 时，比全量排序高效太多。

这个思路也说明了为什么堆结构比堆排序本身更值得掌握：堆排序用堆把整个数组排好序，而 TopK 只需要维持一个窗口，窗口大小固定后，新增元素的替换成本是 O(log K)，空间占用也只是 K。经典的流式数据中位数、滑动窗口最值等题目，本质都是同一套堆操作。

8.2 Java PriorityQueue 与堆排序的关系

Java 的PriorityQueue底层就是一个用数组实现的二叉堆，默认是小顶堆。add和offer方法会执行上浮操作，把新元素放到正确位置；poll方法移除堆顶元素后，会把末尾元素移到堆顶再执行下沉。你会发现，这些操作和堆排序里的siftDown、上浮逻辑如出一辙。

阅读PriorityQueue源码是个很好的巩固练习：看它的siftDown实现，再对比你自己写的版本，就可以理解官方库对边界条件、比较器、扩容的处理方式。理解了堆之后，再看这些源码完全没有障碍，因为底层就是那棵“看不见的完全二叉树”。

8.3 快排、归并、堆排序怎么选

最后聊聊选型建议。通用场景下，Java 直接Arrays.sort就好，JDK 已经针对不同数据类型做了极致优化。如果你正在实现一个自定义排序组件，需要稳定性就选归并排序或其变体；需要最坏情况可预测、额外空间严格受限，堆排序是最稳的选择；链表排序、外部排序这类没法随机访问的场景，归并排序更合适。

堆排序最大的短板是缓存不友好和稳定性缺失。所以在“要不要亲手实现一个堆排序”这个问题上，我的态度是：必须会写，但日常别轻易替换现成的排序库。堆排序的价值更多体现在它培养的思维方式——理解堆的数据结构，才能理解优先队列、理解调度器、理解那些藏在框架底层的高性能组件。从这个角度说，它是投入产出比很高的一笔学习投资。

我个人实际学习中的体会是，堆排序最值得记住的并不是那几行代码，而是“堆”这个结构本身。你把siftDown写熟了，后面看PriorityQueue的源码、看定时器的最小堆、看各种 TopK 场景，都是同一个思路在复用。最后再分享一个小技巧：初学阶段别在电脑前对着代码干看，拿一张纸，写一个 5 到 8 个数的乱序数组，把建堆、交换、下沉每一步的数组状态都画出来。我当年这样走三遍之后，整个算法就再也忘不掉了，后面面试手写堆排序，也只是一个默写动作而已。