简介：本资源是一份面向算法初学者与计算机专业学生的堆排序算法综合实验报告，以Java语言实现，帮助读者系统掌握堆排序的建堆、调整与排序全过程。压缩包内共1个doc文档，约63KB，内容涵盖算法流程图、关键代码、复杂度分析、实验环境说明及心得体会，结构完整，适合课程实验报告参考与算法复习。文档详细讲解了建立初始堆、选出最大元素、调整堆等核心步骤，并给出可直接运行的Java代码，包括buildHeap、heapify、heapSort等关键方法，同时分析了最好、最坏及平均情况下的时间复杂度均为O(nlogn)，空间复杂度为O(1)，并指出堆排序属于不稳定排序。目前已有3943人学习下载，适合需要完成算法实验、理解堆结构或准备面试的读者参考，可快速获取完整实验报告框架与代码实现思路。

1. 堆排序算法：为什么建堆只要 O(n)，而排序却要 O(nlogn)

很多人第一次接触堆排序，都会卡在同一个地方：建堆明明要遍历一半的节点做下沉，为什么复杂度不是 O(nlogn) 而是 O(n)？更反直觉的是，排序阶段只做了 n-1 次取堆顶，复杂度反而是 O(nlogn)。这两个结论放在一起，总让人觉得哪里算错了。

堆排序算法（Heapsort）正是这样一个「结论好记、机制难讲透」的典型。它不依赖递归分治的额外空间，不需要像归并那样开辅助数组，也不像快排那样在极端数据下退化到 O(n²)。它把数组本身当成一棵完全二叉树，用下标运算代替指针，用「下沉」代替递归回溯。理解堆排序，本质上是在理解三件事：完全二叉树的数组映射、堆序的局部修复、以及复杂度分析里那个容易被忽略的求和公式。把这三件事拆开，你会发现它比想象中更精巧，也比教科书里写的更有意思。

2. 堆的数组映射：为什么下标 2i+1 能代替指针

2.1 完全二叉树的顺序存储约定

堆在逻辑上是一棵完全二叉树，但在物理上就是一个普通数组。这个映射关系是整个算法的地基：下标 i 的左孩子是 2i+1，右孩子是 2i+2，父节点是 (i-1)/2 向下取整。这不是随便定的，而是完全二叉树「从上到下、从左到右」逐层编号的自然结果。

用数学归纳法看一眼就明白：根节点编号 0，第一层结束于下标 0；第二层从 1 到 2；第三层从 3 到 6。每一层的起始下标是 2^k - 1，层内第 m 个节点的下标是 2^k - 1 + m。它的左孩子在下一层的第 2m 个位置，代入公式得到 2(2^k - 1 + m) + 1 = 2^(k+1) - 1 + 2m，正好是下一层第 2m 个节点的下标。这个恒等式保证了数组下标和树结构严格对应，不需要任何额外指针。

注意：这套映射只对完全二叉树成立。如果树中间有空缺，数组下标就会错位，堆序也就无从谈起。这也是为什么堆必须维持「完全」这个约束——它不是为了好看，而是为了让下标运算成立。

2.2 最后一个非叶节点的位置

建堆时循环从 n/2 - 1 开始，这个起点不是拍脑袋来的。在完全二叉树中，叶子节点只可能出现在最后两层，且所有叶子节点都集中在数组尾部。最后一个非叶节点，就是最后一个叶子节点的父节点。

最后一个叶子节点的下标是 n-1，它的父节点是 ((n-1)-1)/2 = n/2 - 1。所以从 n/2 - 1 开始往前遍历，每个节点都至少有一个孩子，都需要做一次下沉。从 n/2 到 n-1 这些位置全是叶子，没有孩子，下沉操作会直接返回，遍历它们纯属浪费。这个起点的选择，把建堆的循环次数砍掉了一半。

public void buildHeap(int[] a) { int n = a.length; for (int i = n / 2 - 1; i >= 0; --i) { heapify(a, i, n - 1); } }

这段代码里，i 从 n/2 - 1 递减到 0，每次对以 i 为根的子树做一次 heapify。注意 heapify 的第三个参数是 n-1，表示当前堆的有效范围是整个数组。建堆完成后，a[0] 就是整个数组的最大值。

2.3 为什么从下往上建堆是对的

从 n/2 - 1 往前遍历，意味着先处理底层的小子树，再处理上层的大子树。这个顺序保证了每次 heapify(i) 被调用时，i 的左右子树已经是合法的堆。因为左右孩子的下标都大于 i，而循环是从大到小，所以孩子节点一定已经被处理过了。

如果反过来从上往下建堆，处理根节点时左右子树还是乱的，下沉到一半就可能停在一个「暂时看起来对、但子树内部无序」的位置，最终得到的不是堆。这个顺序依赖是堆排序里少数不能随意调换的步骤之一，写反了不会报错，但排序结果会静默出错。

3. 下沉操作：堆序修复的核心机制

3.1 heapify 的三路比较逻辑

heapify 是整个堆排序里被调用最频繁的函数，它的任务很单一：假设 i 的左右子树都已经是堆，只有 i 这个位置可能违反堆序，把 i 下沉到合适的位置。代码里的三路比较——先比左右孩子选出较大的，再拿这个较大值和根比较——是标准写法。

public void heapify(int[] a, int i, int j) { int left = i * 2 + 1; int right = i * 2 + 2; if (left > j) { return; } int large = left; if (right <= j && a[left] < a[right]) { large = right; } if (a[i] < a[large]) { swap(a, i, large); heapify(a, large, j); } }

参数 j 是当前堆的右边界。建堆时 j = n-1，排序过程中 j 会随着有序区扩大而缩小。left > j 说明 i 已经是叶子，没有孩子可比，直接返回。large 先默认指向左孩子，如果右孩子存在且比左孩子大，就改指右孩子。最后如果根比 large 小，交换并递归下沉。

3.2 递归下沉与迭代下沉的取舍

上面用的是递归写法，逻辑清晰但每次递归都有栈帧开销。实际工程里更常见的是迭代版本，用一个 while 循环代替递归调用：

public void heapifyIterative(int[] a, int i, int j) { while (true) { int left = 2 * i + 1; int right = 2 * i + 2; int large = i; if (left <= j && a[left] > a[large]) large = left; if (right <= j && a[right] > a[large]) large = right; if (large == i) break; swap(a, i, large); i = large; } }

迭代版把「交换后继续下沉」变成了「更新 i 后重新循环」，省掉了递归栈。对于 n 很大的数组，递归深度最多是 log₂n，栈帧总量不大，但迭代版在常数因子上更优。两种写法在复杂度上没有区别，选择哪个更多是风格问题。

3.3 下沉路径的长度上界

一次 heapify 最多走多远？从当前节点走到叶子，路径长度等于该节点的高度。对于下标 i 的节点，它的高度是 ⌊log₂(n/(i+1))⌋ 左右。根节点高度最大，约 log₂n；越靠近底部的节点高度越小，叶子节点高度为 0。

这个「高度随下标增大而减小」的性质，是后面分析建堆复杂度的关键。建堆时对每个非叶节点调用一次 heapify，代价是它的高度。把所有非叶节点的高度加起来，得到的是一个收敛的级数，而不是 n 乘以 logn。

4. 排序阶段：为什么取堆顶 n-1 次是 O(nlogn)

4.1 交换堆顶与堆尾的语义

建堆完成后，a[0] 是全局最大值。排序阶段做的第一件事，是把它和数组最后一个元素交换。这一步的语义是：最大值已经就位，放到它最终应该在的位置。交换后，a[0] 变成了原来堆尾的小元素，堆的有效范围从 n 缩小到 n-1。

public void heapSort(int[] a) { buildHeap(a); for (int i = a.length - 1; i > 0; i--) { swap(a, 0, i); heapify(a, 0, i - 1); } }

循环变量 i 从 n-1 递减到 1。每次 swap(a, 0, i) 把当前堆顶送到位置 i，然后 heapify(a, 0, i-1) 在缩小后的范围内修复堆序。循环结束时，整个数组升序排列。

4.2 每次重建堆的代价为什么是 O(logi)

第 i 次循环时，堆的有效范围是 0 到 i-1，共 i 个元素。堆顶元素被换走后，只有根节点可能违反堆序，其他位置的堆序都还保持。所以只需要对根做一次 heapify，代价是根节点的高度，即 ⌊log₂i⌋。

这里有个容易混淆的点：heapify 的递归深度不是固定的 logn，而是取决于当前堆的大小。第一次循环堆大小是 n，代价 log₂n；最后一次循环堆大小是 2，代价 log₂2 = 1。把 n-1 次循环的代价加起来，得到 Σ⌊log₂i⌋（i 从 2 到 n），这个和的上界是 n·log₂n。所以排序阶段是 O(nlogn)。

4.3 最好、最差、平均为什么都是 O(nlogn)

堆排序对输入数据的初始顺序不敏感。不管原始数组是升序、降序还是随机排列，建堆阶段都要遍历所有非叶节点做下沉，排序阶段都要取 n-1 次堆顶并重建。每个步骤的执行次数只和 n 有关，和数据分布无关。

这和快排形成鲜明对比：快排如果每次选中的枢轴都是极值，递归树退化成链表，复杂度掉到 O(n²)。堆排序没有这个风险，因为堆的结构保证了根到叶的路径长度始终是 logn 级别。代价是它的常数因子比快排大——同样规模的数据，堆排序的实际运行时间通常比快排长，因为它的比较和交换是跳跃式的，缓存局部性差。

5. 建堆 O(n) 的推导：那个被忽略的求和

5.1 逐层求和的正确姿势

建堆复杂度是 O(n) 而不是 O(nlogn)，关键在于不能简单地把「n/2 个节点 × 每个 logn 代价」乘起来。正确的做法是按层求和：高度为 h 的节点有多少个，每个的代价是多少。

在完全二叉树中，高度为 h 的节点数最多是 ⌈n/2^(h+1)⌉。高度为 h 的节点做一次 heapify 的代价是 O(h)。所以总代价是 Σ(h/2^(h+1))·n，h 从 0 到 logn。这个级数 Σh/2^h 是收敛的，收敛到 2。所以总代价是 O(n)。

直观理解：大部分节点都在底层，高度很小，代价接近常数；只有极少数节点在高处，代价才是 logn。把「大多数便宜、少数贵」加权平均，结果就是线性的。

5.2 与排序阶段复杂度的对比

建堆 O(n) 和排序 O(nlogn) 放在一起看，会发现一个有意思的不对称：建堆只做了一次「从无序到堆」的转换，代价是线性的；排序要做 n-1 次「从堆到有序」的转换，每次代价是对数级的。

这个不对称的根源在于：建堆时，每个节点只需要和它的子树比较，子树规模随高度指数衰减；排序时，每次都要从根开始重新下沉，根的高度始终是 logn。换句话说，建堆是「自底向上、代价递减」，排序是「自顶向下、代价恒定」。

5.3 空间复杂度与稳定性

堆排序的空间复杂度是 O(1)，只用了 swap 里的一个临时变量。这是它相对于归并排序的最大优势——归并需要 O(n) 的辅助数组。在内存受限的场景下，这个优势很实在。

但堆排序是不稳定的。交换堆顶和堆尾时，相同值的元素可能被换到彼此前面。比如数组 [5a, 5b, 3]，建堆后可能变成 [5a, 5b, 3]，排序后 5a 和 5b 的相对顺序可能颠倒。如果业务要求稳定排序，堆排序不能直接用，得额外记录原始下标。

6. 避坑与排查：堆排序实现里最容易翻车的几个点

6.1 边界条件写错导致数组越界

现象：运行时报 ArrayIndexOutOfBoundsException，或者排序结果部分正确部分混乱。

原因：heapify 里判断孩子是否存在的条件写成了 left < n 而不是 left <= j。建堆时 j = n-1，两者等价；但排序阶段 j 会缩小，用 n 判断就会访问到已经有序的区域。

解决：heapify 的所有边界判断统一用参数 j，不要混用数组长度 n。left > j 返回，right <= j 才比较右孩子。

6.2 建堆起点写成 n/2 导致漏掉一个节点

现象：排序结果基本正确，但偶尔有一个元素位置不对。

原因：最后一个非叶节点的下标是 n/2 - 1，不是 n/2。如果从 n/2 开始，下标 n/2 - 1 的节点没被处理，它的子树可能违反堆序。

解决：循环写成 for (int i = n/2 - 1; i >= 0; --i)。可以用 n=2 和 n=3 两个小数组手动验证起点是否正确。

6.3 升序排序却建了大顶堆之外的小顶堆

现象：排序结果是降序，或者完全乱序。

原因：堆排序升序需要大顶堆（根是最大值），降序需要小顶堆。如果建堆时比较逻辑写反了，根变成最小值，每次取出的「堆顶」就是最小值，放到数组尾部自然得到降序。

解决：确认 heapify 里的比较方向。升序用 a[left] > a[large] 选大孩子，a[i] < a[large] 时交换。

6.4 递归下沉没有更新边界导致死循环

现象：程序卡死，CPU 占用飙升。

原因：递归调用 heapify(a, large, j) 时，如果 j 没有正确传递，或者 large 的计算有误导致 large == i，就会无限递归。

解决：在交换前确认 large != i，交换后递归的边界参数保持不变。迭代版里用 if (large == i) break 显式终止。

6.5 测试用例只测随机数组漏掉边界

现象：随机数据测试通过，但特定输入出错。

原因：随机数组很少触发 n=0、n=1、全部相同、已经有序这些边界情况。

解决：测试用例至少覆盖空数组、单元素、两元素、全部相同、升序、降序六种情况。项目里的 isHeap 和 isSorted 两个断言函数可以组合使用，先验证建堆结果，再验证排序结果。

7. 从堆排序看算法设计的取舍

堆排序最值得玩味的地方，是它用一套极其朴素的机制——数组下标加下沉——同时拿到了 O(nlogn) 时间、O(1) 空间和全场景稳定性（指复杂度不随输入退化）。这三个性质单独拿出来都不稀奇，但同时满足的排序算法并不多。快排时间更优但最差会退化，归并稳定但费空间，插入排序空间省但时间差一个量级。

代价藏在常数因子里。堆排序的每次比较和交换都是跳跃式的，访问 a[2i+1] 和 a[i] 在内存里可能隔得很远，CPU 缓存命中率低。实际跑起来，同样一千万个整数，堆排序通常比快排慢两到三倍。这不是算法本身的问题，是内存层次结构带来的现实惩罚。

我自己的习惯是：需要原地排序且对最差情况有要求时，优先考虑堆排序；追求平均性能且数据随机时，快排更合适；需要稳定排序时，两者都得让位给归并。理解一个算法的价值，不只是记住它的复杂度，而是知道它在什么条件下会翻车、在什么场景下不可替代。堆排序的不可替代性，就在于它把「原地」和「最差 O(nlogn)」这两个约束同时满足了。

从那以后我每次实现堆排序，都会先用 n=0、n=1、n=2 三个用例跑一遍，再拿随机数组验证 isHeap 和 isSorted，最后才上大规模数据测性能。这套流程帮我省掉了很多次「逻辑看起来对、结果就是不对」的排查时间。希望帮到你。

本文还有配套的精品资源，点击获取