堆排序是一个很有意思的算法它表面上看起来简单无非就是“建个堆然后挨个取最大值”但只要自己动手写过一遍几乎每个人都会在某个细节上卡住——为什么下沉操作要写三个分支为什么从小到大排序反而要构建大顶堆为什么建堆从n//2 - 1开始往前遍历这些问题如果你只是看教程划过去基本等于没学会。我在实际写代码和面试候选人的过程中发现堆排序是那种“看完觉得懂了、合上书写不出来”的典型代表。原因倒不是算法本身有多难而是它的实现细节跟人的直觉反着来。这篇内容我打算把堆排序的完整链路讲透从“为什么需要堆”的本质出发到每一步的Python实现到复杂度推导再到实测中容易踩的坑最后给出几个高频场景的扩展用法。无论你是刚接触算法的初学者还是准备面试需要系统复习这篇文章都值得你完整读一遍最好跟着把代码敲一遍。1. 先搞清楚堆排序到底在排什么从选择排序到堆选择的跃迁1.1 堆排序的本质是选择排序的升级版如果我问你给你一个无序数组让你从小到大排序最朴素的做法是什么绝大多数人第一反应是冒泡、插入或者干脆调sorted()。但我更愿意把堆排序放在“选择排序”这条逻辑线上来理解因为这能解释清楚它为什么存在、以及它的复杂度优势从哪来。选择排序的思路很直白每一轮从未排序区间中找出最小值或最大值放到正确位置上重复 n 轮。每一轮找最小值要扫描整个未排序区间所以找 n 次要扫 n 次时间复杂度是 O(n²)。这个复杂度在数据量小的时候无所谓一旦数据量大到十万、百万级就是灾难。堆排序做的事情本质上跟选择排序一模一样每一轮取出当前未排序区间的最大值或者最小值放到正确位置。但它聪明的地方在于——它用堆这个数据结构来维护“当前最大值”使得每一轮取最大值的代价从 O(n) 降到了 O(log n)。于是整体复杂度从 O(n²) 降到了 O(n log n)。这里最关键的一个认知转变是堆不是一个“排好序的数组”而是一个“能快速获取极值的结构”。它维护的是“当前最大/最小”这一条信息而不是全局的顺序。这也是很多初学者最大的误区——把堆想象成某种二叉搜索树试图用堆直接得到一个完全有序的序列这是错的。堆只保证父节点和子节点之间的序关系不保证兄弟节点之间的序关系。1.2 堆这个数据结构到底长什么样堆在逻辑上是一棵完全二叉树在物理上是一个数组。这两个视角要来回切换才能彻底搞懂堆排序。逻辑视角每个父节点的值都大于等于大顶堆或小于等于小顶堆它的左右孩子。根节点是整个堆的最大值大顶堆或最小值小顶堆。物理视角树的结构被扁平化存储在一个数组里不需要任何指针完全靠下标计算父子关系。对于一个下标从 0 开始的数组如果节点索引是 i那么它的左孩子是2 * i 1右孩子是2 * i 2父节点是(i - 1) // 2。这两个视角的切换是堆排序代码实现的基石。你写的sift_down函数逻辑上在“沿着树往下走”但物理上只是在下标之间跳转。能用数组下标熟练还原出树的结构堆排序就成功了一半。我见过不少人在学堆排序时卡壳就是因为始终停留在“数组一段一段”的思维里没有真正建立起“数组下标对应树节点”的空间感。我的建议是刚开始学的时候拿一张纸把数组[4, 10, 3, 5, 1, 2]对应的完全二叉树画出来再标上每个节点的索引反复对照看几遍后面写代码会顺畅很多。2. 下沉操作堆排序真正吃时间的核心环节2.1 sift_down 到底在做什么堆排序的所有操作最终都归结到一个动作——下沉sift_down。建堆靠下沉排序阶段取完最大值之后恢复堆结构也靠下沉。可以说下沉函数是堆排序的心脏把它写对、写稳整个堆排序就完成了一大半。下沉的语义是假设从某个节点出发它的左子树和右子树都已经各自满足堆的性质但该节点本身可能比它的某个孩子小大顶堆场景下于是这个节点需要“一路往下走”直到它找到合适的位置使整棵子树重新满足堆的性质。用大白话说一个“不够大”的父节点它不配坐在上面的位置上所以要把它往下挪把更大的孩子顶上来。这个过程会沿着树一路传递下去直到抵达某个节点它的两个孩子都比它小它才算安定下来。下沉操作有一个很重要的使用前提——被下沉节点的左右子树必须已经是合法的堆。这一点在排序阶段尤其关键当堆顶与堆尾交换后新的堆顶元素破坏了堆的性质而它的两棵子树因为没有被触碰过仍然各自是合法的堆所以对它执行一次下沉整棵堆就能恢复。这种“只破坏一个局部然后用一次操作修复”的结构正是堆能保持 O(log n) 高效的根本原因。2.2 下沉操作的每一步边界判断用 Python 来实现下沉最朴素也最不容易出错的版本是这个def sift_down(arr, start, end): root start while True: child 2 * root 1 if child end: break if child 1 end and arr[child] arr[child 1]: child 1 if arr[root] arr[child]: arr[root], arr[child] arr[child], arr[root] root child else: break这个函数的三个参数值得认真理解start是待下沉节点的起始位置end是当前堆的有效边界包含。注意这里的end不是数组总长度而是“堆部分最后一个元素的下标”。因为排序过程中数组末尾会逐渐堆积已经排好的最大值这些元素已经不属于堆了下沉过程中绝不能越过end这个边界。这是初学者最容易犯的错误之一——直接用len(arr)作为边界结果在排序阶段把已经排好的元素又拉回堆里导致排序彻底错乱。代码里每一行都是有讲究的child 2 * root 1先找到左孩子。如果左孩子的下标已经超过end说明当前节点是叶子节点没有孩子可以比较直接结束下沉。if child 1 end and arr[child] arr[child 1]这是在两个子节点之间做选择。只有当右孩子存在且比左孩子大时才将child指向右孩子。这保证了child始终指向“两个子节点中较大的那一个”。if arr[root] arr[child]如果父节点比较大的孩子还小说明当前节点不称职交换两者然后让root移动到孩子的位置继续下一轮循环。else: break如果父节点不小于较大的孩子说明它已经站稳了整棵子树已经满足堆性质不需要继续下沉。这个写法把边界条件都收拢在一个while True循环里逻辑非常干净。不过我在面试中见过很多人把child end的判断和child 1 end的判断漏掉导致数组越界或者访问到已经不属于堆的元素。这两个边界判断是下沉函数最容易写崩的地方值得反复默写几遍。2.3 为何采用迭代而非递归很多教材里下沉操作是用递归写的。递归在思路上更贴近“树的自然结构”但我在工程和面试场景里都强烈建议用迭代。原因有三点第一递归会消耗调用栈虽然堆高度是 O(log n)一般不会栈溢出但在 Python 这种默认递归深度受限的语言里用递归写堆排序总让人心里不踏实第二下沉是堆排序中最频繁调用的操作迭代写法避免了函数调用的额外开销性能更好第三迭代写法把“沿着路径移动”的这个过程展现得更直白——变量root像一枚棋子一样在路径上滑动每一步都清晰可追踪排查 bug 时更容易定位。3. 建堆与排序完整流程的每一步拆解3.1 建堆为什么从最后一个非叶子节点开始往上走建堆的目标是让整个数组满足大顶堆性质。最暴力的做法是从左到右逐个插入但更高效的做法是“由下而上地下沉”。具体来说从最后一个非叶子节点开始倒着往前对每个节点执行sift_downdef heapify(arr): n len(arr) for i in range((n - 2) // 2, -1, -1): sift_down(arr, i, n - 1)这里的关键问题是为什么从(n - 2) // 2开始它其实是在求“最后一个非叶子节点的下标”。数组最后一个元素的下标是n - 1根据父节点公式(i - 1) // 2它的父节点就是(n - 1 - 1) // 2 (n - 2) // 2。这个节点是整棵树中下标最大的非叶子节点从它开始往前遍历就能覆盖到所有有孩子的节点。再深一层为什么必须从下往上这个我想了很久才想通其实答案就藏在下沉操作的前提里——sift_down 要求被下沉节点的左右子树已经是合法的堆。对于叶子节点来说空子树天然就是合法的堆所以从倒数第二层开始它们的子树叶子节点已经是合法的堆可以对它们下沉处理完这一层后往上一层节点的子树也都被处理过了于是可以继续下沉。这种自底向上的顺序刚好让每次下沉都满足前置条件。你可以对比一下“逐个插入建堆”的方式每插入一个新元素需要向上调整sift_up到合适位置时间复杂度是 O(n log n)。而自底向上的下沉建堆时间复杂度是 O(n)这个 O(n) 的性质让建堆过程成为堆排序性价比最高的环节。3.2 排序阶段反复“取出堆顶 下沉恢复”建堆完成之后数组的最大值已经位于下标 0 的位置堆顶。排序阶段的操作很机械把堆顶当前最大值与堆数组的最后一个元素交换。这样最大值就位数组末尾开始作为已排序区。堆的有效长度减 1。新的堆顶元素来自数组末尾大概率不满足堆性质对它执行一次sift_down恢复堆。重复上述步骤 n - 1 次直到堆里只剩一个元素。用 Python 写出来就是def heap_sort(arr): heapify(arr) for end in range(len(arr) - 1, 0, -1): arr[0], arr[end] arr[end], arr[0] sift_down(arr, 0, end - 1)这个循环的精妙之处在于变量end的双重身份它既是本次要交换的“堆尾位置”也是交换之后新的堆边界。每次交换结束后end - 1变成新的堆边界这个被排好的最大值就永远躺在堆外面了后续所有下沉操作都无法触及它。这里有一个反直觉的点需要专门强调从小到大排序构建的是大顶堆而不是小顶堆。很多人刚接触时都会想当然地说“从小到大那每次取最小值用小顶堆啊”。问题在于排序阶段我们取出的极值要放在数组的“未排序区间的末尾”取最大值正好可以从后往前填充数组每一步堆的有效区间都在缩小最终得到一个升序数组。如果用小顶堆你确实能拿到最小值但最小值应该放在数组最前面那堆的有效区间如何收缩、如何和数组前部衔接处理起来反而绕。所以标准做法就是升序用大顶堆降序才用小顶堆。这个结论不需要死记画一下取数和放数的位置关系就一目了然了。3.3 一个完整的手动演示为了把流程彻底讲明白我拿一个短数组手动走一遍。假设数组是[4, 10, 3, 5, 1]目标是升序排列。先建堆。数组长度为 5(5 - 2) // 2 1所以从下标 1值为 10开始下沉。它有两个孩子下标 3值 5和下标 4值 1都比 10 小不需要下沉。接着对下标 0值为 4下沉。它的左孩子是下标 1值 10右孩子是下标 2值 3。较大的孩子是 104 比 10 小交换。此时root变为 1继续往下看下标 1 的新孩子是下标 3值 5和下标 4值 1较大的孩子是 5而 4 仍然比 5 小继续交换。此时root变为 3已经是叶子节点下沉结束。建堆后的数组是[10, 5, 3, 4, 1]。注意这个数组并不完全有序你甚至能看到5排在4和3前面但它确实满足大顶堆性质堆顶是最大值 10。排序阶段开始。第一轮堆顶 10 与堆尾 1 交换数组变为[1, 5, 3, 4, 10]堆边界收缩到下标 3。对堆顶 1 下沉较大孩子为 5交换继续下沉较大孩子为 4交换。下沉后数组变为[5, 4, 3, 1, 10]。第二轮堆顶 5 与堆尾 1 交换数组变为[1, 4, 3, 5, 10]堆边界收缩到下标 2。对堆顶 1 下沉较大孩子为 4交换。数组变为[4, 1, 3, 5, 10]。第三轮堆顶 4 与堆尾 3 交换数组变为[3, 1, 4, 5, 10]堆边界收缩到下标 1。堆顶 3 只有左孩子 13 不小于 1不需要下沉。第四轮堆顶 3 与堆尾 1 交换数组变为[1, 3, 4, 5, 10]。堆里剩一个元素排序完成。手动走完一遍之后你会对下沉的语义、堆边界的变化、以及对“为什么已经是升序”这件事有非常直观的体感。我强烈建议你看完这篇文章后自己拿一个长度 7、8 的随机数组在纸上走一遍这个过程的收益远大于看十遍代码。4. 完整Python实现与容易写错的位置4.1 完整可运行的代码把前面几节的代码组装起来加上一个简单的测试入口就是一份可以直接跑的堆排序实现import random def sift_down(arr, start, end): root start while True: child 2 * root 1 if child end: break if child 1 end and arr[child] arr[child 1]: child 1 if arr[root] arr[child]: arr[root], arr[child] arr[child], arr[root] root child else: break def heapify(arr): for i in range((len(arr) - 2) // 2, -1, -1): sift_down(arr, i, len(arr) - 1) def heap_sort(arr): heapify(arr) for end in range(len(arr) - 1, 0, -1): arr[0], arr[end] arr[end], arr[0] sift_down(arr, 0, end - 1) if __name__ __main__: test [random.randint(0, 100) for _ in range(20)] print(排序前:, test) heap_sort(test) print(排序后:, test)这里我用了random.randint生成测试数据全部是 Python 标准库自带的功能不需要额外安装任何第三方包。如果你刚接触 Python 还没装好开发环境直接用系统自带的 IDLE 或者命令行python交互界面都能跑起来。4.2 五个最容易写错的地方写完这份代码我在实际教学和代码评审中还总结出几个高频出错的点值得单独拿出来说。第一下沉边界误用len(arr)。这个前面已经强调过。排序阶段一定要用收缩后的end作为边界写sift_down(arr, 0, end - 1)而不是sift_down(arr, 0, len(arr) - 1)。后者会让已经排好的最大值重新参与堆调整整个排序直接白干。第二左右孩子比较时漏掉右孩子存在的判断。child 1 end这个条件不能省。当child 1正好等于end 1时访问arr[child 1]就会越界。这在对长度不是 2 的幂次的数组排序时特别容易触发。第三交换之后忘记让root child。有些初学者会把交换写成如下形式if arr[root] arr[child]: arr[root], arr[child] arr[child], arr[root]交换完就以为本次下沉结束了。实际上交换后原来的值只是挪到了子节点位置它可能仍然比孙节点小还要继续向下比较。不更新root会导致下沉只进行了一层堆性质没有完全恢复排序结果还是错的。第四建堆的起始下标用n // 2而不是(n - 2) // 2。对于长度为偶数的数组这两个值可能只差 1影响不大但对于长度为奇数的数组n // 2指向的可能是一个叶子节点对它下沉是无用功。倒也不是致命错误但会让学习过程产生困惑。用(n - 2) // 2才是通用且正确的。第五把heapify当成排序。堆化结束后数组只是满足堆性质绝不是有序的。拿到堆化的结果去检验排序成果发现没排好就怀疑代码错了是新手常有的困惑。要时刻记住建堆只是准备工作真正的排序发生在后面的for end循环里。4.3 拆解代码中的几个意图heapify那一步用的是“自底向上的下沉建堆”这是时间上最优的方案。如果改成逐个插入的方式也就是每来一个新元素就做一次向上调整sift_up整体复杂度会退化到 O(n log n)。堆排序总复杂度是 O(n log n)建堆部分若从 O(n) 变为 O(n log n)在大数据量下性能差异虽然没有量级上的变化但常数会明显变大。而且把“向上调整”和“向下调整”两套逻辑混在一份代码里理解负担更重。所以我在这份实现里刻意只用了sift_down一种操作让读者只需要吃透一个核心函数。排序阶段的for end in range(len(arr) - 1, 0, -1)循环总共执行 n - 1 次最后一次循环开始时堆里只剩两个元素交换后剩一个元素就不需要再调整了。倒推到代码层面就是当end 1时交换后sift_down(arr, 0, 0)对应一个节点——一个节点天然就是合法的堆循环结束。这个边界和下沉函数里的if child end: break是吻合的。5. 复杂度与稳定性的严谨推导为什么堆排序实际跑不快5.1 时间复杂度的直觉建立堆排序包含两个阶段建堆和排序。建堆阶段表面上看要对 n/2 个节点做下沉每个下沉最多 O(log n)所以很多人会以为建堆是 O(n log n)。这个“直觉”是错的。关键在于下沉的代价和节点所在的高度有关——越靠近底层的节点虽然数量多但下沉路径很短越靠近顶层的节点下沉路径长但数量很少。把每层的节点数乘以各自的下沉路径长度然后求和得到的是一个以常数比例收敛的级数最终结果就是 O(n)。这个证明思路比硬记结论重要它解释了为什么堆化的总和是 O(n) 而不是 O(n log n)。排序阶段共执行 n - 1 次取堆顶操作每次取完堆顶都要对堆顶做一次下沉下沉的时间复杂度是树的高度 O(log n)所以排序阶段是 O(n log n)。两者相加总的复杂度是 O(n log n)。堆排序在最坏情况下也能达到 O(n log n) 这一点是它相对于快速排序最大的理论优势——快速排序平均是 O(n log n)但最坏退化到 O(n²)。堆排序没有这个弱点。不过实际工程里这个理论优势往往被常数因子抵消后面会细说。空间复杂度方面堆排序是原地排序只需要常数级别的额外空间O(1)。这一点优于归并排序的 O(n)。5.2 稳定性堆排序是不稳定的稳定性的含义是两个相等元素的相对顺序在排序前后保持不变。堆排序是不稳定的。原因也很直观堆排序在交换堆顶和堆尾时距离可能跨越大半个数组两个相等的值在调整过程中完全可能彼此越过。举个例子数组[5a, 5b, 3]用 a、b 区分两个 5。建堆后堆顶是 5a堆尾是 3交换后[3, 5b, 5a]此时 5a 和 5b 的相对位置已经倒过来了。后续排序完成它们的顺序保持这种倒置状态稳定性就被破坏了。这个特性在实际应用中很重要。如果你需要对一个数组先按某个字段排序再按另一个字段排序用不稳定的排序算法可能导致第一轮的排序结果在第二轮被破坏。这种情况下要么用稳定的排序算法如归并排序要么把多个排序字段合并成一个复合字段统一排序。5.3 堆排序在实测中的表现为什么快排总是赢复杂度分析归分析真实世界里堆排序很少成为默认选择。原因在于常数因子。堆排序的每次下沉操作比较的路径是跳跃式的root从数组索引 0 跳到 1再到 3、7、15……这些地址在内存中是跳跃分布的不像归并排序那样按顺序扫描连续的内存区域。CPU 的缓存预取机制对顺序访问非常友好对跳跃访问则无能为力所以堆排序的缓存命中率远低于快排和归并排序。另外堆排序的交换操作也比快排更频繁。快排的分区过程中每个元素平均只被比较和交换常数次而堆排序在“下沉”过程中要不断比较父节点和子节点一次节点调整可能产生多次交换。实测下来同样的数据量堆排序的运行时间通常是快排的 1.5 到 2 倍以上。我在处理百万级数据量时简单对比过Python 内置的sorted()底层是 TimSort一种归并和插入的混合排序比手写的堆排序快了差不多一个数量级。所以日常开发中直接调sorted()永远是第一选择手写堆排序的意义在于理解算法思想、应对面试、以及在堆结构本身能派上用场的场景比如 TopK、优先队列、定时器任务调度里灵活运用。6. 测试、调试与实战从验证算法到解决TopK问题6.1 怎么验证你的堆排序写对了写完代码第一件事不是看结果而是做系统性的测试。我推荐一个组合随机数组 暴力验证 边界用例。随机数组测试就是生成大量长度随机、值域随机的数组排序后用arr sorted(arr)验证结果。这一步能覆盖绝大多数逻辑错误。边界用例要专门覆盖这些情况空数组[]、单元素数组[1]、两个元素[2, 1]和[1, 2]、所有元素相同的数组[3, 3, 3]、已经有序的数组、完全逆序的数组。我见过一个实现其他情况全对唯独在单元素数组上抛异常因为排序循环里end从 0 开始时出了问题。边界用例专门治这种毛病。还有一个非常有用的调试技巧在sift_down函数开头加一行断言检查传入的堆范围是否有效def sift_down(arr, start, end): assert 0 start end len(arr), finvalid heap range: {start} {end} ...一旦边界算错断言立刻帮你定位到是哪个环节传入了非法范围。实际调试时这比肉眼盯代码高效得多。调试完再删掉断言或者留着也无妨它只会在异常时影响性能。6.2 从堆排序到 TopK一个每个后端都会遇到的实战场景堆排序本身在工程里用得少但堆这种结构在“从海量数据里取前 K 个最大/最小元素”这个问题上是无可替代的。经典的 TopK 思路是这样的先取前 K 个元素建一个小顶堆如果是求最大的 K 个然后遍历剩余元素每来一个元素就和堆顶比较——堆顶是当前最小的那个如果新元素比堆顶大就替换堆顶并下沉。遍历结束后堆里剩下的就是最大的 K 个。时间复杂度 O(n log K)空间 O(K)。当 K 远小于 n 时这个算法的优势是决定性的。我举个例子说明它的实用价值。假设内存只能装下 100 万个整数但数据总量有 10 亿个要找出最大的 100 个。全量排序显然不现实——数据根本装不进内存。TopK 方案只需要维护一个容量为 100 的小顶堆遍历一遍数据内存占用恒定搞完就是答案。这在日志分析、排行榜、推荐系统召回等场景里都是标配做法。用 Python 写 TopK 甚至不需要自己实现堆标准库的heapq直接帮你搞定import heapq def top_k_largest(nums, k): heap nums[:k] heapq.heapify(heap) for x in nums[k:]: if x heap[0]: heapq.heapreplace(heap, x) return heap这个函数的时间复杂度同样是 O(n log K)但heapq是 C 语言实现的比自己写的 Python 版本快很多。面试时如果你能先把heapq的用法讲清楚再手动实现一遍核心下沉逻辑会显得既有工程经验又有算法功底是加分项。6.3 堆排序的另一个隐藏用途求第 K 大元素TopK 之外“求第 K 大元素”也是堆的经典应用。思路和 TopK 完全一致维护一个容量为 K 的小顶堆遍历完整数组后堆顶就是第 K 大的元素。注意这里堆顶是“第 K 大”而不是“第 K 小”——因为堆里保存的是最大的 K 个堆顶是这 K 个中最小的那个也就是所有数里第 K 大的。在 Python 里同样可以用heapq轻松写出import heapq def find_kth_largest(nums, k): heap nums[:k] heapq.heapify(heap) for x in nums[k:]: if x heap[0]: heapq.heapreplace(heap, x) return heap[0]我第一次看到这段代码时愣了一下——它只比 TopK 少了一行返回语句。这其实揭示了一个重要的思维模式TopK 和第 K 大是同一个问题的两面理解了堆的维护机制两者就是一个函数的事。这种“把类型问题抽象成通用解法”的能力比背下某一道题的标准答案值钱得多。关于第 K 大问题还有一个值得了解的最优解——快速选择算法Quickselect它的平均时间复杂度是 O(n)优于堆方案的 O(n log K)。但快速选择的最坏情况是 O(n²)而且需要把整个数组加载进内存无法处理流式数据。所以在面对流式数据、或者不确定数据总量时堆方案依然是更稳妥的选择。最后再说几句实在话堆排序是我觉得性价比最高的排序算法之一代码量不大但里面有“物理结构 vs 逻辑结构”“自底向上的归纳”“用单一核心操作完成全流程”“复杂度推导的反直觉”等多个值得反复品味的点。我自己的体感是把它彻底写对一次堆、树、递归三块知识会同时上一个台阶。如果你刚写完一遍就跑出了正确结果可以再试试不看代码重新默写一遍如果卡住了别急着看答案先画一棵树一步一步模拟下沉过程往往很快就能找到自己的思维盲区。这个查漏补缺的过程比多刷几道算法题有用得多。 
长河君 · 2026/10/10 1:53:30 · 阅读 1.2k 堆排序算法完全解析：从下沉操作到Python实现与TopK实战
堆排序是一个很有意思的算法它表面上看起来简单无非就是“建个堆然后挨个取最大值”但只要自己动手写过一遍几乎每个人都会在某个细节上卡住——为什么下沉操作要写三个分支为什么从小到大排序反而要构建大顶堆为什么建堆从n//2 - 1开始往前遍历这些问题如果你只是看教程划过去基本等于没学会。我在实际写代码和面试候选人的过程中发现堆排序是那种“看完觉得懂了、合上书写不出来”的典型代表。原因倒不是算法本身有多难而是它的实现细节跟人的直觉反着来。这篇内容我打算把堆排序的完整链路讲透从“为什么需要堆”的本质出发到每一步的Python实现到复杂度推导再到实测中容易踩的坑最后给出几个高频场景的扩展用法。无论你是刚接触算法的初学者还是准备面试需要系统复习这篇文章都值得你完整读一遍最好跟着把代码敲一遍。1. 先搞清楚堆排序到底在排什么从选择排序到堆选择的跃迁1.1 堆排序的本质是选择排序的升级版如果我问你给你一个无序数组让你从小到大排序最朴素的做法是什么绝大多数人第一反应是冒泡、插入或者干脆调sorted()。但我更愿意把堆排序放在“选择排序”这条逻辑线上来理解因为这能解释清楚它为什么存在、以及它的复杂度优势从哪来。选择排序的思路很直白每一轮从未排序区间中找出最小值或最大值放到正确位置上重复 n 轮。每一轮找最小值要扫描整个未排序区间所以找 n 次要扫 n 次时间复杂度是 O(n²)。这个复杂度在数据量小的时候无所谓一旦数据量大到十万、百万级就是灾难。堆排序做的事情本质上跟选择排序一模一样每一轮取出当前未排序区间的最大值或者最小值放到正确位置。但它聪明的地方在于——它用堆这个数据结构来维护“当前最大值”使得每一轮取最大值的代价从 O(n) 降到了 O(log n)。于是整体复杂度从 O(n²) 降到了 O(n log n)。这里最关键的一个认知转变是堆不是一个“排好序的数组”而是一个“能快速获取极值的结构”。它维护的是“当前最大/最小”这一条信息而不是全局的顺序。这也是很多初学者最大的误区——把堆想象成某种二叉搜索树试图用堆直接得到一个完全有序的序列这是错的。堆只保证父节点和子节点之间的序关系不保证兄弟节点之间的序关系。1.2 堆这个数据结构到底长什么样堆在逻辑上是一棵完全二叉树在物理上是一个数组。这两个视角要来回切换才能彻底搞懂堆排序。逻辑视角每个父节点的值都大于等于大顶堆或小于等于小顶堆它的左右孩子。根节点是整个堆的最大值大顶堆或最小值小顶堆。物理视角树的结构被扁平化存储在一个数组里不需要任何指针完全靠下标计算父子关系。对于一个下标从 0 开始的数组如果节点索引是 i那么它的左孩子是2 * i 1右孩子是2 * i 2父节点是(i - 1) // 2。这两个视角的切换是堆排序代码实现的基石。你写的sift_down函数逻辑上在“沿着树往下走”但物理上只是在下标之间跳转。能用数组下标熟练还原出树的结构堆排序就成功了一半。我见过不少人在学堆排序时卡壳就是因为始终停留在“数组一段一段”的思维里没有真正建立起“数组下标对应树节点”的空间感。我的建议是刚开始学的时候拿一张纸把数组[4, 10, 3, 5, 1, 2]对应的完全二叉树画出来再标上每个节点的索引反复对照看几遍后面写代码会顺畅很多。2. 下沉操作堆排序真正吃时间的核心环节2.1 sift_down 到底在做什么堆排序的所有操作最终都归结到一个动作——下沉sift_down。建堆靠下沉排序阶段取完最大值之后恢复堆结构也靠下沉。可以说下沉函数是堆排序的心脏把它写对、写稳整个堆排序就完成了一大半。下沉的语义是假设从某个节点出发它的左子树和右子树都已经各自满足堆的性质但该节点本身可能比它的某个孩子小大顶堆场景下于是这个节点需要“一路往下走”直到它找到合适的位置使整棵子树重新满足堆的性质。用大白话说一个“不够大”的父节点它不配坐在上面的位置上所以要把它往下挪把更大的孩子顶上来。这个过程会沿着树一路传递下去直到抵达某个节点它的两个孩子都比它小它才算安定下来。下沉操作有一个很重要的使用前提——被下沉节点的左右子树必须已经是合法的堆。这一点在排序阶段尤其关键当堆顶与堆尾交换后新的堆顶元素破坏了堆的性质而它的两棵子树因为没有被触碰过仍然各自是合法的堆所以对它执行一次下沉整棵堆就能恢复。这种“只破坏一个局部然后用一次操作修复”的结构正是堆能保持 O(log n) 高效的根本原因。2.2 下沉操作的每一步边界判断用 Python 来实现下沉最朴素也最不容易出错的版本是这个def sift_down(arr, start, end): root start while True: child 2 * root 1 if child end: break if child 1 end and arr[child] arr[child 1]: child 1 if arr[root] arr[child]: arr[root], arr[child] arr[child], arr[root] root child else: break这个函数的三个参数值得认真理解start是待下沉节点的起始位置end是当前堆的有效边界包含。注意这里的end不是数组总长度而是“堆部分最后一个元素的下标”。因为排序过程中数组末尾会逐渐堆积已经排好的最大值这些元素已经不属于堆了下沉过程中绝不能越过end这个边界。这是初学者最容易犯的错误之一——直接用len(arr)作为边界结果在排序阶段把已经排好的元素又拉回堆里导致排序彻底错乱。代码里每一行都是有讲究的child 2 * root 1先找到左孩子。如果左孩子的下标已经超过end说明当前节点是叶子节点没有孩子可以比较直接结束下沉。if child 1 end and arr[child] arr[child 1]这是在两个子节点之间做选择。只有当右孩子存在且比左孩子大时才将child指向右孩子。这保证了child始终指向“两个子节点中较大的那一个”。if arr[root] arr[child]如果父节点比较大的孩子还小说明当前节点不称职交换两者然后让root移动到孩子的位置继续下一轮循环。else: break如果父节点不小于较大的孩子说明它已经站稳了整棵子树已经满足堆性质不需要继续下沉。这个写法把边界条件都收拢在一个while True循环里逻辑非常干净。不过我在面试中见过很多人把child end的判断和child 1 end的判断漏掉导致数组越界或者访问到已经不属于堆的元素。这两个边界判断是下沉函数最容易写崩的地方值得反复默写几遍。2.3 为何采用迭代而非递归很多教材里下沉操作是用递归写的。递归在思路上更贴近“树的自然结构”但我在工程和面试场景里都强烈建议用迭代。原因有三点第一递归会消耗调用栈虽然堆高度是 O(log n)一般不会栈溢出但在 Python 这种默认递归深度受限的语言里用递归写堆排序总让人心里不踏实第二下沉是堆排序中最频繁调用的操作迭代写法避免了函数调用的额外开销性能更好第三迭代写法把“沿着路径移动”的这个过程展现得更直白——变量root像一枚棋子一样在路径上滑动每一步都清晰可追踪排查 bug 时更容易定位。3. 建堆与排序完整流程的每一步拆解3.1 建堆为什么从最后一个非叶子节点开始往上走建堆的目标是让整个数组满足大顶堆性质。最暴力的做法是从左到右逐个插入但更高效的做法是“由下而上地下沉”。具体来说从最后一个非叶子节点开始倒着往前对每个节点执行sift_downdef heapify(arr): n len(arr) for i in range((n - 2) // 2, -1, -1): sift_down(arr, i, n - 1)这里的关键问题是为什么从(n - 2) // 2开始它其实是在求“最后一个非叶子节点的下标”。数组最后一个元素的下标是n - 1根据父节点公式(i - 1) // 2它的父节点就是(n - 1 - 1) // 2 (n - 2) // 2。这个节点是整棵树中下标最大的非叶子节点从它开始往前遍历就能覆盖到所有有孩子的节点。再深一层为什么必须从下往上这个我想了很久才想通其实答案就藏在下沉操作的前提里——sift_down 要求被下沉节点的左右子树已经是合法的堆。对于叶子节点来说空子树天然就是合法的堆所以从倒数第二层开始它们的子树叶子节点已经是合法的堆可以对它们下沉处理完这一层后往上一层节点的子树也都被处理过了于是可以继续下沉。这种自底向上的顺序刚好让每次下沉都满足前置条件。你可以对比一下“逐个插入建堆”的方式每插入一个新元素需要向上调整sift_up到合适位置时间复杂度是 O(n log n)。而自底向上的下沉建堆时间复杂度是 O(n)这个 O(n) 的性质让建堆过程成为堆排序性价比最高的环节。3.2 排序阶段反复“取出堆顶 下沉恢复”建堆完成之后数组的最大值已经位于下标 0 的位置堆顶。排序阶段的操作很机械把堆顶当前最大值与堆数组的最后一个元素交换。这样最大值就位数组末尾开始作为已排序区。堆的有效长度减 1。新的堆顶元素来自数组末尾大概率不满足堆性质对它执行一次sift_down恢复堆。重复上述步骤 n - 1 次直到堆里只剩一个元素。用 Python 写出来就是def heap_sort(arr): heapify(arr) for end in range(len(arr) - 1, 0, -1): arr[0], arr[end] arr[end], arr[0] sift_down(arr, 0, end - 1)这个循环的精妙之处在于变量end的双重身份它既是本次要交换的“堆尾位置”也是交换之后新的堆边界。每次交换结束后end - 1变成新的堆边界这个被排好的最大值就永远躺在堆外面了后续所有下沉操作都无法触及它。这里有一个反直觉的点需要专门强调从小到大排序构建的是大顶堆而不是小顶堆。很多人刚接触时都会想当然地说“从小到大那每次取最小值用小顶堆啊”。问题在于排序阶段我们取出的极值要放在数组的“未排序区间的末尾”取最大值正好可以从后往前填充数组每一步堆的有效区间都在缩小最终得到一个升序数组。如果用小顶堆你确实能拿到最小值但最小值应该放在数组最前面那堆的有效区间如何收缩、如何和数组前部衔接处理起来反而绕。所以标准做法就是升序用大顶堆降序才用小顶堆。这个结论不需要死记画一下取数和放数的位置关系就一目了然了。3.3 一个完整的手动演示为了把流程彻底讲明白我拿一个短数组手动走一遍。假设数组是[4, 10, 3, 5, 1]目标是升序排列。先建堆。数组长度为 5(5 - 2) // 2 1所以从下标 1值为 10开始下沉。它有两个孩子下标 3值 5和下标 4值 1都比 10 小不需要下沉。接着对下标 0值为 4下沉。它的左孩子是下标 1值 10右孩子是下标 2值 3。较大的孩子是 104 比 10 小交换。此时root变为 1继续往下看下标 1 的新孩子是下标 3值 5和下标 4值 1较大的孩子是 5而 4 仍然比 5 小继续交换。此时root变为 3已经是叶子节点下沉结束。建堆后的数组是[10, 5, 3, 4, 1]。注意这个数组并不完全有序你甚至能看到5排在4和3前面但它确实满足大顶堆性质堆顶是最大值 10。排序阶段开始。第一轮堆顶 10 与堆尾 1 交换数组变为[1, 5, 3, 4, 10]堆边界收缩到下标 3。对堆顶 1 下沉较大孩子为 5交换继续下沉较大孩子为 4交换。下沉后数组变为[5, 4, 3, 1, 10]。第二轮堆顶 5 与堆尾 1 交换数组变为[1, 4, 3, 5, 10]堆边界收缩到下标 2。对堆顶 1 下沉较大孩子为 4交换。数组变为[4, 1, 3, 5, 10]。第三轮堆顶 4 与堆尾 3 交换数组变为[3, 1, 4, 5, 10]堆边界收缩到下标 1。堆顶 3 只有左孩子 13 不小于 1不需要下沉。第四轮堆顶 3 与堆尾 1 交换数组变为[1, 3, 4, 5, 10]。堆里剩一个元素排序完成。手动走完一遍之后你会对下沉的语义、堆边界的变化、以及对“为什么已经是升序”这件事有非常直观的体感。我强烈建议你看完这篇文章后自己拿一个长度 7、8 的随机数组在纸上走一遍这个过程的收益远大于看十遍代码。4. 完整Python实现与容易写错的位置4.1 完整可运行的代码把前面几节的代码组装起来加上一个简单的测试入口就是一份可以直接跑的堆排序实现import random def sift_down(arr, start, end): root start while True: child 2 * root 1 if child end: break if child 1 end and arr[child] arr[child 1]: child 1 if arr[root] arr[child]: arr[root], arr[child] arr[child], arr[root] root child else: break def heapify(arr): for i in range((len(arr) - 2) // 2, -1, -1): sift_down(arr, i, len(arr) - 1) def heap_sort(arr): heapify(arr) for end in range(len(arr) - 1, 0, -1): arr[0], arr[end] arr[end], arr[0] sift_down(arr, 0, end - 1) if __name__ __main__: test [random.randint(0, 100) for _ in range(20)] print(排序前:, test) heap_sort(test) print(排序后:, test)这里我用了random.randint生成测试数据全部是 Python 标准库自带的功能不需要额外安装任何第三方包。如果你刚接触 Python 还没装好开发环境直接用系统自带的 IDLE 或者命令行python交互界面都能跑起来。4.2 五个最容易写错的地方写完这份代码我在实际教学和代码评审中还总结出几个高频出错的点值得单独拿出来说。第一下沉边界误用len(arr)。这个前面已经强调过。排序阶段一定要用收缩后的end作为边界写sift_down(arr, 0, end - 1)而不是sift_down(arr, 0, len(arr) - 1)。后者会让已经排好的最大值重新参与堆调整整个排序直接白干。第二左右孩子比较时漏掉右孩子存在的判断。child 1 end这个条件不能省。当child 1正好等于end 1时访问arr[child 1]就会越界。这在对长度不是 2 的幂次的数组排序时特别容易触发。第三交换之后忘记让root child。有些初学者会把交换写成如下形式if arr[root] arr[child]: arr[root], arr[child] arr[child], arr[root]交换完就以为本次下沉结束了。实际上交换后原来的值只是挪到了子节点位置它可能仍然比孙节点小还要继续向下比较。不更新root会导致下沉只进行了一层堆性质没有完全恢复排序结果还是错的。第四建堆的起始下标用n // 2而不是(n - 2) // 2。对于长度为偶数的数组这两个值可能只差 1影响不大但对于长度为奇数的数组n // 2指向的可能是一个叶子节点对它下沉是无用功。倒也不是致命错误但会让学习过程产生困惑。用(n - 2) // 2才是通用且正确的。第五把heapify当成排序。堆化结束后数组只是满足堆性质绝不是有序的。拿到堆化的结果去检验排序成果发现没排好就怀疑代码错了是新手常有的困惑。要时刻记住建堆只是准备工作真正的排序发生在后面的for end循环里。4.3 拆解代码中的几个意图heapify那一步用的是“自底向上的下沉建堆”这是时间上最优的方案。如果改成逐个插入的方式也就是每来一个新元素就做一次向上调整sift_up整体复杂度会退化到 O(n log n)。堆排序总复杂度是 O(n log n)建堆部分若从 O(n) 变为 O(n log n)在大数据量下性能差异虽然没有量级上的变化但常数会明显变大。而且把“向上调整”和“向下调整”两套逻辑混在一份代码里理解负担更重。所以我在这份实现里刻意只用了sift_down一种操作让读者只需要吃透一个核心函数。排序阶段的for end in range(len(arr) - 1, 0, -1)循环总共执行 n - 1 次最后一次循环开始时堆里只剩两个元素交换后剩一个元素就不需要再调整了。倒推到代码层面就是当end 1时交换后sift_down(arr, 0, 0)对应一个节点——一个节点天然就是合法的堆循环结束。这个边界和下沉函数里的if child end: break是吻合的。5. 复杂度与稳定性的严谨推导为什么堆排序实际跑不快5.1 时间复杂度的直觉建立堆排序包含两个阶段建堆和排序。建堆阶段表面上看要对 n/2 个节点做下沉每个下沉最多 O(log n)所以很多人会以为建堆是 O(n log n)。这个“直觉”是错的。关键在于下沉的代价和节点所在的高度有关——越靠近底层的节点虽然数量多但下沉路径很短越靠近顶层的节点下沉路径长但数量很少。把每层的节点数乘以各自的下沉路径长度然后求和得到的是一个以常数比例收敛的级数最终结果就是 O(n)。这个证明思路比硬记结论重要它解释了为什么堆化的总和是 O(n) 而不是 O(n log n)。排序阶段共执行 n - 1 次取堆顶操作每次取完堆顶都要对堆顶做一次下沉下沉的时间复杂度是树的高度 O(log n)所以排序阶段是 O(n log n)。两者相加总的复杂度是 O(n log n)。堆排序在最坏情况下也能达到 O(n log n) 这一点是它相对于快速排序最大的理论优势——快速排序平均是 O(n log n)但最坏退化到 O(n²)。堆排序没有这个弱点。不过实际工程里这个理论优势往往被常数因子抵消后面会细说。空间复杂度方面堆排序是原地排序只需要常数级别的额外空间O(1)。这一点优于归并排序的 O(n)。5.2 稳定性堆排序是不稳定的稳定性的含义是两个相等元素的相对顺序在排序前后保持不变。堆排序是不稳定的。原因也很直观堆排序在交换堆顶和堆尾时距离可能跨越大半个数组两个相等的值在调整过程中完全可能彼此越过。举个例子数组[5a, 5b, 3]用 a、b 区分两个 5。建堆后堆顶是 5a堆尾是 3交换后[3, 5b, 5a]此时 5a 和 5b 的相对位置已经倒过来了。后续排序完成它们的顺序保持这种倒置状态稳定性就被破坏了。这个特性在实际应用中很重要。如果你需要对一个数组先按某个字段排序再按另一个字段排序用不稳定的排序算法可能导致第一轮的排序结果在第二轮被破坏。这种情况下要么用稳定的排序算法如归并排序要么把多个排序字段合并成一个复合字段统一排序。5.3 堆排序在实测中的表现为什么快排总是赢复杂度分析归分析真实世界里堆排序很少成为默认选择。原因在于常数因子。堆排序的每次下沉操作比较的路径是跳跃式的root从数组索引 0 跳到 1再到 3、7、15……这些地址在内存中是跳跃分布的不像归并排序那样按顺序扫描连续的内存区域。CPU 的缓存预取机制对顺序访问非常友好对跳跃访问则无能为力所以堆排序的缓存命中率远低于快排和归并排序。另外堆排序的交换操作也比快排更频繁。快排的分区过程中每个元素平均只被比较和交换常数次而堆排序在“下沉”过程中要不断比较父节点和子节点一次节点调整可能产生多次交换。实测下来同样的数据量堆排序的运行时间通常是快排的 1.5 到 2 倍以上。我在处理百万级数据量时简单对比过Python 内置的sorted()底层是 TimSort一种归并和插入的混合排序比手写的堆排序快了差不多一个数量级。所以日常开发中直接调sorted()永远是第一选择手写堆排序的意义在于理解算法思想、应对面试、以及在堆结构本身能派上用场的场景比如 TopK、优先队列、定时器任务调度里灵活运用。6. 测试、调试与实战从验证算法到解决TopK问题6.1 怎么验证你的堆排序写对了写完代码第一件事不是看结果而是做系统性的测试。我推荐一个组合随机数组 暴力验证 边界用例。随机数组测试就是生成大量长度随机、值域随机的数组排序后用arr sorted(arr)验证结果。这一步能覆盖绝大多数逻辑错误。边界用例要专门覆盖这些情况空数组[]、单元素数组[1]、两个元素[2, 1]和[1, 2]、所有元素相同的数组[3, 3, 3]、已经有序的数组、完全逆序的数组。我见过一个实现其他情况全对唯独在单元素数组上抛异常因为排序循环里end从 0 开始时出了问题。边界用例专门治这种毛病。还有一个非常有用的调试技巧在sift_down函数开头加一行断言检查传入的堆范围是否有效def sift_down(arr, start, end): assert 0 start end len(arr), finvalid heap range: {start} {end} ...一旦边界算错断言立刻帮你定位到是哪个环节传入了非法范围。实际调试时这比肉眼盯代码高效得多。调试完再删掉断言或者留着也无妨它只会在异常时影响性能。6.2 从堆排序到 TopK一个每个后端都会遇到的实战场景堆排序本身在工程里用得少但堆这种结构在“从海量数据里取前 K 个最大/最小元素”这个问题上是无可替代的。经典的 TopK 思路是这样的先取前 K 个元素建一个小顶堆如果是求最大的 K 个然后遍历剩余元素每来一个元素就和堆顶比较——堆顶是当前最小的那个如果新元素比堆顶大就替换堆顶并下沉。遍历结束后堆里剩下的就是最大的 K 个。时间复杂度 O(n log K)空间 O(K)。当 K 远小于 n 时这个算法的优势是决定性的。我举个例子说明它的实用价值。假设内存只能装下 100 万个整数但数据总量有 10 亿个要找出最大的 100 个。全量排序显然不现实——数据根本装不进内存。TopK 方案只需要维护一个容量为 100 的小顶堆遍历一遍数据内存占用恒定搞完就是答案。这在日志分析、排行榜、推荐系统召回等场景里都是标配做法。用 Python 写 TopK 甚至不需要自己实现堆标准库的heapq直接帮你搞定import heapq def top_k_largest(nums, k): heap nums[:k] heapq.heapify(heap) for x in nums[k:]: if x heap[0]: heapq.heapreplace(heap, x) return heap这个函数的时间复杂度同样是 O(n log K)但heapq是 C 语言实现的比自己写的 Python 版本快很多。面试时如果你能先把heapq的用法讲清楚再手动实现一遍核心下沉逻辑会显得既有工程经验又有算法功底是加分项。6.3 堆排序的另一个隐藏用途求第 K 大元素TopK 之外“求第 K 大元素”也是堆的经典应用。思路和 TopK 完全一致维护一个容量为 K 的小顶堆遍历完整数组后堆顶就是第 K 大的元素。注意这里堆顶是“第 K 大”而不是“第 K 小”——因为堆里保存的是最大的 K 个堆顶是这 K 个中最小的那个也就是所有数里第 K 大的。在 Python 里同样可以用heapq轻松写出import heapq def find_kth_largest(nums, k): heap nums[:k] heapq.heapify(heap) for x in nums[k:]: if x heap[0]: heapq.heapreplace(heap, x) return heap[0]我第一次看到这段代码时愣了一下——它只比 TopK 少了一行返回语句。这其实揭示了一个重要的思维模式TopK 和第 K 大是同一个问题的两面理解了堆的维护机制两者就是一个函数的事。这种“把类型问题抽象成通用解法”的能力比背下某一道题的标准答案值钱得多。关于第 K 大问题还有一个值得了解的最优解——快速选择算法Quickselect它的平均时间复杂度是 O(n)优于堆方案的 O(n log K)。但快速选择的最坏情况是 O(n²)而且需要把整个数组加载进内存无法处理流式数据。所以在面对流式数据、或者不确定数据总量时堆方案依然是更稳妥的选择。最后再说几句实在话堆排序是我觉得性价比最高的排序算法之一代码量不大但里面有“物理结构 vs 逻辑结构”“自底向上的归纳”“用单一核心操作完成全流程”“复杂度推导的反直觉”等多个值得反复品味的点。我自己的体感是把它彻底写对一次堆、树、递归三块知识会同时上一个台阶。如果你刚写完一遍就跑出了正确结果可以再试试不看代码重新默写一遍如果卡住了别急着看答案先画一棵树一步一步模拟下沉过程往往很快就能找到自己的思维盲区。这个查漏补缺的过程比多刷几道算法题有用得多。