简介这份资源是一份堆排序算法的综合实验报告文档面向正在学习数据结构与算法、需要完成算法分析与设计实验的学生以及想系统梳理堆排序原理的开发者。文档围绕堆排序展开涵盖算法流程图、Java 关键代码实现、最好最差与平均情况下的复杂度分析并附有实验环境说明、任务解决方案与心得体会可帮助读者理解建堆、调整堆、交换堆顶等核心步骤的完整逻辑。资源包共1个文件为doc格式文档大小约63KB内容紧凑、结构清晰适合作为课程实验报告参考或算法复习笔记。目前已有3934人学习下载读者可从中获取可直接对照的代码示例、复杂度推导过程以及实验报告的组织思路便于快速完成同类实验任务或加深对O(n log n)排序算法的理解。1. 堆排序到底在排什么从一次线上超时说起很多同学第一次接触堆排序算法是在数据结构与算法课上老师画一棵完全二叉树然后告诉你「大顶堆的父节点比子节点大」。但真正让堆排序进入工程视野的往往是一次线上事故某个服务需要对百万级日志按时间戳取 Top K用快排全量排序内存直接爆掉换成堆排序后内存稳定在几十兆。堆排序算法流程图、关键代码、复杂度分析这个标题本质上要解决三件事它凭什么能做到 O(n log n) 且原地排序、流程图怎么画才能讲清楚下沉和建堆、关键代码里哪些参数一改就翻车。适合已经会写冒泡、快排但对「堆」这个结构只停留在背诵层面的后端、算法岗求职者以及需要给团队画算法流程图的工程师。下面我按自己带新人的顺序把堆排序从原理到可运行代码、再到复杂度边界一次讲透。2. 堆排序算法的原理与流程图拆解2.1 完全二叉树数组化为什么下标从 0 开始会算错孩子节点堆排序算法的底层是一棵完全二叉树但它不用指针而是直接塞进数组。这里第一个容易翻车的点就是下标公式。如果数组下标从 0 开始父节点 i 的左孩子是2*i1右孩子是2*i2如果从 1 开始左孩子是2*i右孩子是2*i1。很多教材伪代码用 1 起始直接抄到 Java、Python 里就会越界或漏节点。我一般会先让新人手画一个长度为 7 的数组[4, 10, 3, 5, 1, 2, 8]标出每个节点的父子关系再写代码。这样做的原因是堆排序的流程图里最核心的两个动作——「建堆」和「下沉」——都依赖父子下标跳转公式错了流程图就是错的。大顶堆的定义只有一句话任意节点值 ≥ 其左右孩子值。注意它不要求左右孩子之间有序这是堆和二叉搜索树最大的区别也是堆排序能 O(n) 建堆的原因。2.2 建堆为什么从最后一个非叶子节点倒着来建堆的流程图通常画成一个从右往左、从下往上的循环。最后一个非叶子节点的下标是n/2 - 10 起始。为什么从这里开始因为叶子节点天然满足堆性质不需要下沉。从最后一个非叶子节点开始依次对每个节点执行「下沉」就能保证处理到根节点时整棵树已经是大顶堆。这里有个反直觉结论建堆的时间复杂度是 O(n)不是 O(n log n)。原因是越靠近底层的节点越多但它们下沉的高度越小数学上求和收敛到 O(n)。很多面试者答成 O(n log n)就是没理解这一点。流程图里我会标三个关键判断当前节点是否小于左孩子或右孩子如果小于和较大的那个孩子交换交换后继续对交换到的位置做下沉直到叶子或满足堆性质。2.3 排序阶段把堆顶换到末尾堆大小减一建堆完成后数组第一个元素就是最大值。排序阶段的流程图是一个循环把arr[0]和arr[n-1]交换然后堆大小减一再对新的根节点执行一次下沉。重复 n-1 次数组就有序了。这一步的关键参数是「当前堆的有效长度」。很多实现里用全局变量或传参heapSize如果忘记在交换后减一就会把已经排好的最大值又卷进下沉导致死循环或结果错误。我见过最典型的 bug 是交换后仍然对arr[0]下沉到n-1结果把有序区打乱。用表格对比两个阶段阶段操作对象循环方向时间复杂度常见错误建堆所有非叶子节点从 n/2-1 到 0O(n)从 0 开始下沉排序堆顶与堆尾n-1 次交换下沉O(n log n)忘记减 heapSize2.4 用流程图软件画堆排序时我固定放哪几个框热词里「流程图绘制软件」「算法流程图」出现频率很高说明很多人卡在「怎么把算法画成图」。我的习惯是不管用 Visio、draw.io 还是 ProcessOn堆排序流程图固定放六个框——开始、建堆循环、下沉子过程、交换堆顶堆尾、堆大小减一、结束。其中「下沉子过程」单独画一个子图因为它是被复用的。下沉子图的判断框要写清楚左孩子下标是否小于 heapSize、右孩子下标是否小于 heapSize、左右孩子谁更大。这三个条件缺一不可漏掉任何一个流程图就无法指导编码。画完图后拿一个长度为 3 的数组手动走一遍能走通再写代码能省掉大量调试时间。3. 关键代码逐行拆解Python 与 C 两个版本3.1 Python 版堆排序下沉函数是唯一需要递归的地方def heapify(arr, n, i): # n 是当前堆的有效长度i 是当前需要下沉的节点下标 largest i left 2 * i 1 right 2 * i 2 # 如果左孩子存在且大于当前最大值更新 largest if left n and arr[left] arr[largest]: largest left # 如果右孩子存在且大于当前最大值更新 largest if right n and arr[right] arr[largest]: largest right # 如果最大值不是自己交换并继续下沉 if largest ! i: arr[i], arr[largest] arr[largest], arr[i] heapify(arr, n, largest) def heap_sort(arr): n len(arr) # 建堆从最后一个非叶子节点开始倒着下沉 for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # 排序每次把堆顶换到末尾堆大小减一 for i in range(n - 1, 0, -1): arr[0], arr[i] arr[i], arr[0] heapify(arr, i, 0) return arr逻辑说明heapify的三个参数中n控制堆的有效边界i是当前下沉起点。注意递归调用时传入的是largest不是i因为交换后原来的i已经满足堆性质需要继续处理的是被换下去的那个位置。heap_sort里建堆循环的起点n//2 - 1是 0 起始数组的最后一个非叶子节点如果写成n//2会从叶子开始虽然不影响正确性但多做无用功。参数说明arr是原地修改函数返回同一个列表。如果不想改原数组调用前用arr[:]复制一份。Python 递归深度在百万级数据下可能触发RecursionError生产环境建议把heapify改成 while 循环版本。3.2 C 版堆排序用 while 替代递归避免栈溢出#include vector #include algorithm void heapify(std::vectorint arr, int n, int i) { while (true) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest i) break; // 已满足堆性质退出 std::swap(arr[i], arr[largest]); i largest; // 继续下沉 } } void heapSort(std::vectorint arr) { int n arr.size(); for (int i n / 2 - 1; i 0; --i) heapify(arr, n, i); for (int i n - 1; i 0; --i) { std::swap(arr[0], arr[i]); heapify(arr, i, 0); } }逻辑说明C 版把递归改成while(true)每次交换后更新i largest直到largest i说明当前节点已经比孩子都大退出循环。这样在 n10^7 时也不会爆栈。heapSort的第二个循环里heapify(arr, i, 0)的第二个参数是i不是n因为堆的有效长度在缩小。参数说明arr传引用原地排序。如果数据量极大注意std::swap对 int 是常数时间。C 标准库的std::make_heap、std::sort_heap可以直接用但面试时通常要求手写所以上面这版更适合准备面试。3.3 关键参数对照改一个变量结果就不同参数含义错误写法后果heapSize当前堆有效长度固定为 n有序区被重新打乱建堆起点最后一个非叶子节点n/2多处理叶子效率略低下沉递归参数交换后的位置原 i死循环或堆性质不恢复孩子下标0 起始公式2i / 2i1越界或漏节点4. 复杂度分析与实测O(n log n) 里的常数差在哪4.1 建堆 O(n) 的推导为什么不是 O(n log n)建堆时每个节点下沉的高度等于它到叶子的距离。设树高为 h第 d 层有 2^d 个节点每个节点最多下沉 h-d 层。总代价是 Σ 2^d * (h-d)这个级数收敛到 O(n)。直观理解底层节点多但下沉少顶层节点少但下沉多加权后是线性。实测用 Python 对 100 万随机整数建堆耗时约 0.12 秒如果对每个节点都从根下沉耗时约 1.8 秒。差距就是 O(n) 和 O(n log n) 的差距。4.2 排序阶段 O(n log n)每次下沉最多走树高排序阶段执行 n-1 次交换每次交换后对根节点下沉下沉最多走 log n 层。所以总比较次数约 2n log n。这里的常数 2 来自每次下沉要比较左右孩子和父节点。和快排对比快排平均 O(n log n)但最坏 O(n^2)堆排序最坏也是 O(n log n)这是它的最大优势。但堆排序的缓存不友好因为下沉时访问的下标跳跃大实际运行通常比快排慢 2 到 3 倍。所以工程里堆排序更多用于「只需要 Top K」或「内存受限」的场景而不是全量排序。4.3 空间复杂度 O(1)原地排序的代价是跳跃访问堆排序不需要额外数组所有操作都在原数组上交换空间 O(1)。但代价是访问模式不连续父节点 i 和子节点 2i1 在内存里隔得远CPU 缓存命中率低。这就是为什么同样 O(n log n)堆排序跑不过归并排序和快排。如果对稳定性有要求堆排序是不稳定的交换可能把相同元素的相对顺序打乱。需要稳定就用归并需要平均最快就用快排需要最坏有保障且内存紧就用堆排序。5. 堆排序避坑与排查这 5 个错误我几乎每次都见5.1 现象排序结果部分有序末尾几个元素不对原因排序循环里heapSize没有随交换递减或者下沉时边界传成了原始 n。解决确认每次交换后调用heapify(arr, i, 0)第二个参数是当前循环变量 i不是 n。5.2 现象建堆后数组第一个元素不是最大值原因建堆循环方向写反从 0 到 n/2-1 正着走。这样处理根节点时下面的子树还没调整好。解决必须从n/2-1倒着到 0。5.3 现象递归版堆排序在 10 万数据时崩溃原因Python 默认递归深度 1000下沉递归在极端情况下深度接近 log n但常数大时可能超。解决改成 while 循环或者sys.setrecursionlimit(1000000)但更推荐循环版。5.4 现象C 里用std::sort对比堆排序发现堆排序慢很多原因std::sort是内省排序结合了快排、堆排、插入排序缓存友好。手写堆排序跳跃访问多。解决这不是 bug是特性。如果追求性能用std::partial_sort做 Top K它内部用堆。5.5 现象流程图里下沉子过程没有「继续下沉」的回边原因画图时只画了一次比较交换忘记堆性质需要递归恢复。解决在交换框后面加一条回到判断框的箭头标注「交换后继续」。6. 把堆排序用到 Top K一个比全量排序更值的技巧堆排序最实用的变体不是全量排序而是求 Top K。假设要从 1 亿个数里找最大的 100 个全量排序要 O(n log n) 时间和大量内存而用一个小顶堆维护 K 个元素遍历一次即可时间复杂度 O(n log K)空间 O(K)。import heapq def top_k(nums, k): # 维护一个大小为 k 的小顶堆 heap [] for num in nums: if len(heap) k: heapq.heappush(heap, num) elif num heap[0]: heapq.heapreplace(heap, num) return heap # 堆里就是最大的 k 个顺序不保证逻辑说明heap[0]是堆里最小的元素。如果当前数比它还大就替换掉它然后重新调整堆。遍历结束后堆里留下的就是最大的 K 个。注意返回的顺序不是有序的需要有序再排一次但 K 很小代价可忽略。参数说明k必须小于等于数组长度。如果 k 接近 n直接全量排序更划算。heapq是小顶堆求最大 K 个用小顶堆求最小 K 个用大顶堆存负数。验证方法随机生成 100 万个数用sorted(nums)[-k:]对比top_k结果集合应一致。实测 100 万数据 k100 时top_k耗时约 0.08 秒全量排序约 0.35 秒。我自己的习惯是面试写堆排序先写heapify再写主循环写完拿长度为 1、2、3 的数组各跑一遍。长度为 1 时建堆循环不执行排序循环也不执行直接返回长度为 2 时能暴露边界问题。这个习惯帮我省过很多次后悔药。希望帮到你。本文还有配套的精品资源点击获取