简介这份资源是一份面向算法学习者的堆排序综合实验报告适合正在学习数据结构与算法分析、需要完成课程实验或准备面试的读者。内容围绕堆排序展开涵盖算法流程图、Java关键代码实现、最好最差及平均情况下的复杂度分析并附有实验环境说明与心得体会。压缩包内共1个doc文件约63KB以实验报告文档形式呈现结构完整便于直接参考或作为实验模板使用。目前已有3943人学习下载。读者可从中获取建堆与调整堆的完整代码、复杂度推导过程以及实验任务解决方案尤其适合需要理解O(n log n)时间复杂度和O(1)空间复杂度、并希望结合代码验证排序正确性的学习者。报告还包含测试用例与断言方法能帮助读者快速复现实验并加深对堆排序稳定性和适用场景的理解。1. 堆排序算法从实验报告到能跑通的 Java 实现我拆了一遍一份算法实验报告里堆排序的代码往往只有几十行但真正把它跑通、把复杂度讲清楚、把边界情况测出来中间隔着一堆细节。我拿到这份「堆排序算法流程图、关键代码、复杂度分析」资源时第一反应是它能不能直接当模板用翻完代码和复杂度推导后结论是——能但得先搞明白它为什么这么写。这份资源适合正在做算法分析与设计实验的学生、准备面试时想手写堆排序的开发者以及需要一份可验证 Java 实现来对照自己代码的人。它把建堆、调整、交换三个核心动作拆开了还附了 JUnit 测试用例比只贴一段heapSort的博客扎实得多。下面我按「先看懂结构、再跑通代码、最后避开坑」的顺序把这份资源拆成能直接抄作业的步骤。2. 堆排序的核心结构完全二叉树怎么映射到数组2.1 大顶堆与小顶堆的选型差异堆排序的第一步是建堆。这份资源里buildHeap和heapify的写法实际建的是大顶堆——heapify里比较的是a[i] a[large]把较大的子节点往上换最终a[0]是最大值。摘要描述里写的是「小顶堆」但代码逻辑和注释「此时 a[0] 就是最大的元素」都指向大顶堆。这不是错误而是排序方向的选择大顶堆排升序小顶堆排降序。如果你照摘要去理解可能会在调试时发现「怎么排出来是反的」。常见做法是要升序就用大顶堆每次把堆顶最大值换到数组末尾要降序就用小顶堆把最小值换到末尾。这份资源选的是升序路线和isSorted测试用例的断言方向一致。选型理由不复杂堆排序的核心操作是「取堆顶 调整堆」大顶堆的堆顶是当前未排序部分的最大值换到末尾后末尾自然形成有序区。如果用小顶堆换到末尾的就是最小值最终得到降序数组。两者时间复杂度一样区别只在比较符号和最终顺序。资源里的heapify用a[left] a[right]选较大的子节点再用a[i] a[large]判断是否交换这套符号组合就是大顶堆的标准写法。2.2 数组下标与父子节点关系堆是一棵完全二叉树但代码里没有用指针或节点对象而是直接用数组下标算父子关系。这份资源里写得很明确int left 2 * i 1; // 左节点 int right 2 * i 2; // 右节点这是 0-based 数组的映射方式。如果换成 1-based 数组左孩子是2*i右孩子是2*i1父节点是i/2。很多教材用 1-based 讲堆导致直接抄公式到 Java 里会越界或错位。这份资源用 0-based和 Java 数组习惯一致但你在对照教材流程图时要注意转换。buildHeap里从n / 2 - 1开始往前遍历这个起点是最后一个非叶子节点。为什么是n/2 - 1因为最后一个叶子节点的下标是n-1它的父节点是(n-1-1)/2 n/2 - 1。从最后一个非叶子节点开始依次对每个节点做heapify就能保证整棵树变成堆。这个顺序不能反——如果从根开始调整下面的子树还没成堆调整完根之后子树又乱了。从下往上、从右往左是建堆的正确方向。2.3 建堆与排序两阶段的边界划分heapSort方法把整个流程分成两段public void heapSort(int[] a) { buildHeap(a); // 第一阶段建堆a[0] 是最大值 for (int i a.length - 1; i 0; i--) { swap(a, 0, i); // 把堆顶换到末尾 heapify(a, 0, i - 1); // 第二阶段调整剩余部分 } }注意heapify(a, 0, i - 1)的第三个参数是i - 1不是i。因为下标i的位置已经放了当前最大值属于有序区不能再参与堆调整。heapify的第三个参数j表示堆的有效范围是[0, j]。如果写成i就会把已排序的元素又拉回堆里导致排序结果错误。这个边界是手写堆排序时最容易翻车的地方之一。循环条件是i 0不是i 0。当i 0时只剩一个元素天然有序不需要再交换和调整。如果写成i 0会多一次无意义的swap(a, 0, 0)和heapify(a, 0, -1)虽然结果可能不变但逻辑上多余而且heapify里left j的判断会直接返回不会报错但属于冗余操作。3. 关键代码逐段拆解heapify 的递归与终止条件3.1 heapify 的参数含义与递归路径heapify是堆排序里最核心的方法资源里的实现如下public void heapify(int[] a, int i, int j) { int left i * 2 1; int right i * 2 2; if (left j) { // 没有左子树说明 i 是叶子节点 return; } int large left; // 先假设左孩子是较大的 if (right j a[left] a[right]) { large right; // 右孩子存在且更大更新 large } if (a[i] a[large]) { // 根比 large 小交换 swap(a, i, large); heapify(a, large, j); // 继续调整被交换下去的节点 } }参数i是当前要调整的子树根节点j是堆的有效右边界。left j是递归终止条件——如果左孩子下标都超出范围说明i是叶子不需要调整。这里只判断left j而不判断right因为完全二叉树里如果左孩子不存在右孩子一定不存在。large先初始化为left然后检查右孩子是否存在且比左孩子大。注意条件是right j不是right j。因为j是有效下标right j时右孩子是存在的。如果写成right j会漏掉右孩子刚好在边界上的情况导致选错较大子节点。交换之后递归调用heapify(a, large, j)因为被换下去的节点可能比它新的子节点小需要继续下沉。这个递归是尾递归形式但 Java 不优化尾递归所以极端情况下递归深度是树高O(log n)不会栈溢出。如果数据量特别大可以改成循环但这份资源的递归写法更直观。3.2 buildHeap 的遍历起点与调整顺序public void buildHeap(int[] a) { int n a.length; for (int i n / 2 - 1; i 0; --i) { heapify(a, i, n - 1); } }n / 2 - 1是最后一个非叶子节点。以数组{50, 20, 90, 50, 30, 40, 60, 25}为例长度 8n/2 - 1 3下标 3 的元素是 50它有左孩子下标 7值 25没有右孩子。从下标 3 开始往前依次调整下标 2、1、0。每次heapify的边界都是n - 1因为建堆阶段整个数组都是堆的范围。这里有个细节heapify(a, i, n - 1)的第三个参数是n - 1不是n。如果传nleft j的判断会变成left n而left最大是2*(n/2-1)1 n-1永远不会大于n递归就不会因为叶子节点而终止可能导致数组越界。传n - 1是正确做法。3.3 测试用例的验证逻辑资源里附了两个 JUnit 测试Test public void testIsHeap() { int[] a { 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 }; assertTrue(isHeap(a, 0)); } Test public void heapSortTest() { int[] array {50, 20, 90, 50, 30, 40, 60, 25}; heapSort(array); assertTrue(isSorted(array)); print(array); }isHeap是一个递归校验方法检查每个节点是否大于等于其左右孩子。testIsHeap用的数组{16, 14, 10, 8, 7, 9, 3, 2, 4, 1}本身已经是一个合法大顶堆所以断言通过。这个测试验证的是isHeap方法本身不是buildHeap的结果。如果你想验证建堆是否正确应该先对一个无序数组调buildHeap再用isHeap检查。heapSortTest用的数组包含重复元素 50排序后isSorted检查相邻元素是否非递减。这个测试覆盖了重复值的情况但isSorted只检查ary[i] ary[i1]返回 false等于的情况不报错所以对重复值是宽容的。如果你需要严格验证排序结果可以再加一个assertArrayEquals对比预期数组。print方法用System.out.println逐行输出在 JUnit 测试里直接打印到控制台。如果测试运行器不捕获标准输出你可能看不到结果。常见做法是改用Arrays.toString(array)或把结果收集到日志里。4. 复杂度分析与实测验证O(n log n) 到底怎么算4.1 建堆 O(n) 的推导逻辑资源里对建堆复杂度的描述是「从最下层最右边的非终端结点开始构建每个非终端结点最多进行两次比较和互换整个构建堆的时间复杂度为 O(n)」。这个结论是对的但「最多两次比较和互换」的说法容易让人误解——heapify里递归下沉时每个节点可能比较多次不是固定两次。更准确的推导是建堆时每个节点下沉的最大距离是它到叶子节点的高度。对于高度为h的节点调整代价是O(h)。完全二叉树中高度为h的节点数最多为n / 2^(h1)。总代价是Σ (n / 2^(h1)) * h这个级数收敛到O(n)。直观理解大部分节点都在底层下沉距离很短根节点虽然下沉距离长但只有一个。所以建堆比「每个节点都做一次 O(log n) 调整」的 O(n log n) 要快。资源里说「最多进行两次比较和互换」指的是单次heapify调用中选较大子节点一次比较判断是否交换一次比较交换后递归下去。但递归下去之后还有比较所以总比较次数是路径长度。这个表述不够严谨但结论 O(n) 没问题。4.2 排序阶段 O(n log n) 的构成排序阶段循环n - 1次每次swap是 O(1)heapify(a, 0, i - 1)的调整范围逐渐缩小但最坏情况下每次调整的路径长度是当前堆高度约为log i。总代价是Σ log ii 从 n 到 2即O(n log n)。资源里写「第 i 次取堆顶记录重建堆需要用 O(log2 i) 的时间」这里的log2 i是当前堆大小的对数。随着 i 减小调整代价也在减小但总和仍然是O(n log n)。最好、最差、平均都是O(n log n)因为堆排序对原始数据顺序不敏感——无论输入是否有序建堆和调整的路径长度只取决于树结构不取决于元素值分布。空间复杂度是 O(1)因为只用了swap里的临时变量t。递归调用heapify会占用栈空间深度为O(log n)如果算上递归栈空间是O(log n)。资源里说「只有一个用来交换的暂存单元」忽略了递归栈。如果改成迭代版heapify空间才是严格 O(1)。这一点在面试时如果被追问要能区分「额外数组空间」和「递归栈空间」。4.3 用 JUnit 跑一遍验证把资源里的代码整理成一个可运行的 Java 文件加上main方法import java.util.Arrays; public class HeapSortDemo { public static void main(String[] args) { int[] array {50, 20, 90, 50, 30, 40, 60, 25}; System.out.println(排序前: Arrays.toString(array)); heapSort(array); System.out.println(排序后: Arrays.toString(array)); System.out.println(是否有序: isSorted(array)); } public static void heapSort(int[] a) { buildHeap(a); for (int i a.length - 1; i 0; i--) { swap(a, 0, i); heapify(a, 0, i - 1); } } public static void buildHeap(int[] a) { int n a.length; for (int i n / 2 - 1; i 0; --i) { heapify(a, i, n - 1); } } public static 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); } } public static void swap(int[] a, int i, int j) { int t a[i]; a[i] a[j]; a[j] t; } public static boolean isSorted(int[] ary) { for (int i 0; i ary.length - 1; i) { if (ary[i] ary[i 1]) return false; } return true; } }运行后输出排序前: [50, 20, 90, 50, 30, 40, 60, 25] 排序后: [20, 25, 30, 40, 50, 50, 60, 90] 是否有序: true重复元素 50 保留了两个顺序没有要求稳定所以结果正确。如果你想验证建堆阶段可以在buildHeap后打印数组应该看到a[0]是 90。提示heapify的递归深度是O(log n)对百万级数据也不会栈溢出。但如果数据量上亿递归调用次数仍然可观可以改成while循环下沉。5. 避坑与排查堆排序手写时最容易翻车的 5 个点5.1 现象排序结果部分有序但整体不对原因heapify的边界参数传错。常见的是在heapSort循环里写成heapify(a, 0, i)而不是heapify(a, 0, i - 1)导致已排序的末尾元素被重新拉进堆里调整破坏了有序区。解决确认heapify第三个参数是i - 1表示堆的有效范围到i - 1为止。可以在heapify开头加一行if (i j) return;做防御但根本还是参数要对。5.2 现象数组越界异常ArrayIndexOutOfBoundsException原因heapify里判断右孩子时用了right j而不是right j或者buildHeap里传了n而不是n - 1。当right j时右孩子是存在的用会漏掉传n会让left j永远不成立递归到叶子之后继续往下算下标超出数组长度。解决右孩子判断用right jbuildHeap和heapSort里heapify的边界都用n - 1或i - 1。可以在heapify开头加if (i j) return;作为兜底。5.3 现象建堆后a[0]不是最大值原因buildHeap的遍历起点写成了n / 2而不是n / 2 - 1或者遍历方向是从 0 到n/2 - 1。从n/2开始会跳过最后一个非叶子节点从前往后调整会导致子树还没成堆就调整根最终根不是最大值。解决起点用n / 2 - 1方向从后往前i--。可以在buildHeap后加一句assert isHeap(a, 0);验证。5.4 现象递归heapify导致栈溢出原因heapify的递归终止条件写错比如if (left j) return;而不是if (left j) return;。当left j时左孩子是存在的应该继续调整用会提前返回导致堆性质被破坏。更严重的是如果终止条件完全缺失递归会无限下沉。解决终止条件用left j表示左孩子下标超出有效范围才返回。如果担心递归深度可以改成迭代public static void heapifyIterative(int[] a, int i, int j) { while (true) { int left i * 2 1; int right i * 2 2; if (left j) break; int large left; if (right j a[left] a[right]) { large right; } if (a[i] a[large]) break; swap(a, i, large); i large; } }5.5 现象JUnit 测试通过但控制台没有输出原因print方法用System.out.println逐行打印但 JUnit 测试运行器可能不显示标准输出或者输出被截断。另外print方法在heapSortTest里调用如果测试失败断言先抛出异常print不会执行。解决把print改成System.out.println(Arrays.toString(array))或者在测试里用assertEquals对比预期数组。如果只是想看排序结果直接跑main方法更直观。6. 进阶技巧用堆排序思路解 Top-K 问题堆排序的代码稍作改动就能解决「从海量数据中找前 K 个最大元素」的问题。不需要对整个数组排序只需要维护一个大小为 K 的小顶堆遍历数组时如果元素比堆顶大就替换堆顶并调整堆。最终堆里就是前 K 个最大元素。这个思路在面试和实际工程里都很常见时间复杂度是O(n log K)比全排序的O(n log n)更高效。基于这份资源的heapify我改了一个topK方法public static int[] topK(int[] nums, int k) { if (k 0 || k nums.length) { throw new IllegalArgumentException(k 超出范围); } int[] heap new int[k]; System.arraycopy(nums, 0, heap, 0, k); // 建小顶堆把 heapify 的比较方向反过来 for (int i k / 2 - 1; i 0; i--) { heapifyMin(heap, i, k - 1); } for (int i k; i nums.length; i) { if (nums[i] heap[0]) { heap[0] nums[i]; heapifyMin(heap, 0, k - 1); } } return heap; } private static void heapifyMin(int[] a, int i, int j) { int left i * 2 1; int right i * 2 2; if (left j) return; int small left; if (right j a[left] a[right]) { small right; } if (a[i] a[small]) { swap(a, i, small); heapifyMin(a, small, j); } }和原版heapify的区别只有比较符号a[left] a[right]选较小的子节点a[i] a[small]判断是否交换。这样建的是小顶堆堆顶是当前 K 个元素里最小的。遍历时如果遇到比堆顶大的元素就替换堆顶并重新调整。最终堆里保留的就是最大的 K 个。测试一下public static void main(String[] args) { int[] nums {50, 20, 90, 50, 30, 40, 60, 25}; int[] result topK(nums, 3); System.out.println(Top-3: Arrays.toString(result)); }输出Top-3: [50, 60, 90]顺序不保证但元素正确。如果需要按顺序输出可以对结果再排一次序K 很小的时候代价可以忽略。这个技巧的价值在于当数据量大到内存放不下、或者只需要部分排序时堆排序的「部分调整」特性比全排序更合适。我一般会在面试里用这个例子说明堆排序不只是「排个序」而是一种「动态维护极值」的数据结构。从那以后我每次写堆排序都会顺手把heapify的比较方向抽成参数方便在最大堆和最小堆之间切换省得重新推导一遍边界。希望帮到你。本文还有配套的精品资源点击获取