提到“堆排序Heap sort”很多人第一反应是又一个要背的排序算法。但我在实际工作里见过太多人把“排序”和“维护优先级”混为一谈才意识到这个算法背后的思想比算法本身值钱得多。有次我帮一个同事看线上问题他写了个任务调度逻辑任务列表几百个每个任务带优先级。他的做法是每执行完一个任务就把整个列表按优先级重新排一遍然后取第一个。听上去没毛病对吧但你想执行完一个任务之后剩下的几百个任务之间的相对顺序根本没有变你只需要拿到当前最大的那一个。一次全排序是 O(n log n)而用堆的话取最大元素和重新调整都只需要 O(log n)。这个差距在数据量上来之后非常明显。所以他需要的不是“把数组变成有序序列”而是“维护一个能快速取出最大元素的集合”。这就是堆的本质也是堆排序能成为经典算法的原因。这篇文章我会从堆排序的底层数据结构讲起把建堆、排序、复杂度这些环节一块块拆开最后再聊几个实际写代码时容易踩的坑。不管你是准备面试想现场手写堆排序还是在读源码的时候碰到优先队列的实现又或者只是想搞清楚为什么很多语言的内置排序算法不是堆排序这篇应该都能帮到你。1. 堆排序解决的是哪一类问题1.1 从一次代码评审中的“反复排序”说起先说开头那个任务调度的例子。同事的原始代码大概长这样tasks [ {priority: 3, name: A}, {priority: 8, name: B}, {priority: 1, name: C}, # ... ] while tasks: tasks.sort(keylambda x: x[priority], reverseTrue) task tasks.pop(0) execute(task)这段代码的问题很明显每执行一个任务就做一次全量排序。假设任务有 1000 个第一次排序 O(n log n)之后每次都把剩下的数据重新排一遍。如果任务执行过程还有新任务进来那每次插入也是一次全排序的代价。正确的思路是任务之间的相对顺序不重要重要的只有“下一个该执行谁”。这时候一个二叉堆就够了——插入 O(log n)取出最大值 O(log n)并且不需要任何额外的全量排序。我后来把代码改成了用堆实现的任务调度器核心逻辑是import heapq from dataclasses import dataclass dataclass(orderTrue) class Task: priority: int name: str tasks_heap [] heapq.heappush(tasks_heap, Task(3, A)) heapq.heappush(tasks_heap, Task(8, B)) heapq.heappush(tasks_heap, Task(1, C)) while tasks_heap: task heapq.heappop(tasks_heap) execute(task)同样的 effect维护成本完全不同。这个场景告诉我们堆排序不只是“给一个数组排序”的算法它更是一种组织数据的方式。理解堆排序本质上就是在理解“动态集合中的最大/最小值维护”这个更底层的问题。1.2 堆排序与其他排序算法的分工既然聊排序就得说清楚一件事堆排序不是一个“比快排更强”的算法它们是不同场景下的不同选择。看下面这张表算法平均时间复杂度最坏时间复杂度空间复杂度稳定性缓存友好度快速排序O(n log n)O(n²)O(log n) 栈空间不稳定较好归并排序O(n log n)O(n log n)O(n)稳定一般堆排序O(n log n)O(n log n)O(1)不稳定较差插入排序O(n²)O(n²)O(1)稳定很好堆排序独有的优势是什么它是“最坏也有 O(n log n) 原地排序 O(1) 空间”的算法。快速排序大多数时候表现很好但一旦遇到不合理的基准点选择最坏会退化到 O(n²)。归并排序虽然稳定且复杂度有保证但需要额外 O(n) 的辅助空间。堆排序在这两点上是刚的不管输入数据长什么样时间复杂度稳稳的 O(n log n)空间只要放原数组的那点内存。这也是为什么很多标准库里的排序在特定条件下会切换到堆排序。最典型的就是“内省排序”先走快排如果递归深度异常了立刻转成堆排序来兜底保证整体不退化。所以堆排序不是被时代淘汰的算法它是快排背后那个兜底的保险丝。1.3 堆排序适合什么场景说结论吧我理解的合适场景有这几个需要“最坏情况也有保证”的排序且空间要求苛刻比如在某些嵌入式环境、内存受限但数据规模固定的排序任务。作为算法面试的基础功手写堆排序几乎是考察“递归分治 抽象数据结构 下标操作”的综合题。理解更复杂的堆应用Top K 问题、优先队列、定时器、图算法里的最小堆等等。这些应用真正流行的原因是因为堆能在“动态插入”和“取极值”之间保持平衡这是任何一次全排序都做不到的。至于平常业务代码里给一个数组排序真的用内置sort就够了。没必要自己造轮子。但了解堆排序的原理是你能“正确使用和不使用”它的前提。2. 先把二叉堆这个数据结构搞明白2.1 完全二叉树的数组表示法堆排序依赖的底层数据结构是二叉堆Binary Heap。最直观的理解方式是把二叉堆看成“一棵完全二叉树存储在数组里”。完全二叉树的意思是除了最后一层其他每一层都是满的最后一层的节点从左到右连续排放。正是因为结构是“紧凑”的所以我们能用数组存放它而不是像普通二叉树那样用指针。假设根节点放在数组下标 0 的位置那么对于任意下标i的节点它的左右孩子、父节点的下标是固定规律左孩子下标2 * i 1右孩子下标2 * i 2父节点下标(i - 1) // 2我写过一个直观的例子。数组[10, 9, 8, 5, 1, 3, 2, 4]对应下标关系节点下标值左孩子下标左孩子值右孩子下标右孩子值01019281935412853623574--这个映射关系是堆排序所有下标计算的根基。写代码的时候你其实不是在“操作一棵树”而是在“操作一维数组”但脑子里必须随时能把它还原成一棵树。2.2 最大堆的两条不变式二叉堆分最大堆和最小堆。堆排序通常用最大堆来排升序。最大堆要满足两条规则它是完全二叉树数组里没有“空洞”。对任意节点i它的值不小于它的左孩子和右孩子的值arr[i] arr[2*i1]且arr[i] arr[2*i2]前提是孩子存在。由第二条可以推出一个很关键的性质堆顶也就是数组的第一个元素一定是整个数组的最大值。这保证了我们每次“取堆顶”都能拿到当前范围内的最大元素。最小堆正好相反父节点小于等于孩子堆顶是集合中的最小值。有一点要特别说明堆不是完全有序数组。它只保证“层级之间有序”——父大子小但同一层的节点之间谁大谁小完全随意。比如[10, 9, 8, 5, 1, 3, 2, 4]这个堆里左子树和右子树之间的节点就没有可比性。这恰恰是堆高效的原因它只维护了一种“局部强弱关系”维护成本比完全排序低得多。2.3 为什么堆比“全排序”更适合动态场景回到任务调度的例子。如果我用一个有序数组来维护任务列表新增一个任务时必须把数组中的元素往后挪来腾出位置最坏要 O(n)如果用普通排序每次插入重新全排序那更糟糕。而二叉堆的新增操作上浮和删除堆顶操作下沉都只需要 O(log n)。这就是数据结构“用部分有序换维护效率”的经典思路。堆排序也正是利用这种特性先构建一个最大堆然后反复取出堆顶像挤牙膏一样把元素一个个按从大到小的顺序挤出来从而实现排序。3. 建堆阶段为什么从最后一个非叶子节点开始3.1 heapify 的标准动作堆排序里最核心的操作叫heapify下沉调整。它的作用是假设某个节点的左右子树都已经是合法的最大堆但这个节点本身可能比它的孩子小那么把它“下沉”到合适的位置使整棵子树重新成为最大堆。标准实现如下def heapify(arr, n, i): largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left 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)这段代码的逻辑很简单比较大根节点i、左孩子、右孩子三者谁的值最大。如果最大值不是当前节点就把它和最大的孩子交换。交换之后原来最大的孩子位置现在放的是原来的父节点它可能仍然比它的新孩子小所以要递归地继续下沉。为什么要求左右子树“已经是合法堆”因为heapify不是一个从零开始建堆的过程而是一个“修复过程”。它默认的是问题只出在根节点上子树内部已经合规。这个前提很关键后面建堆时我们会利用它。3.2 自底向上建堆的推导如果给你一个完全乱的数组怎么构建一个最大堆一个自然的想法是从数组最后往前逐个调用heapify。但细想一下只要子树不是堆heapify的假设就不成立。所以更合理的顺序是从最后一个非叶子节点开始往前处理到根节点。为什么是最后一个非叶子节点因为再往后的节点全是叶子节点。叶子节点没有孩子天然满足最大堆的性质一个节点比“不存在的孩子”大这当然成立。所以完全不需要处理它们。那么最后一个非叶子节点的下标怎么求对于长度为n的数组最后一个元素的下标是n-1它的父节点就是(n-1-1) // 2 n//2 - 1。所以建堆的循环起点是n // 2 - 1。代码for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i)从后往前处理处理到某个节点时它的左右子树一定已经各自成为合法的堆。因为它的孩子下标更大已经在前面的循环里处理过了。这样每个heapify调用的前置条件都成立。这里有个很容易踩的误区有人会把建堆循环写成从 0 到 n 正向扫一遍。那样做的话先处理的上层节点其下层子树可能还没堆化heapify的递归调整依然可能把乱序传下去最终结果往往得不到一个正确的堆。正确的方向永远是自底向上。3.3 一个完整数组的建堆演示拿一个比较直观的例子数组[4, 10, 3, 5, 1, 8, 2, 9]长度 8所以n // 2 - 1 3。我们从下标 3 开始往前调整。第一步处理下标 3 的节点值为 5。它的左孩子是下标 7值为 9右孩子不存在。9 5交换[4, 10, 3, 9, 1, 8, 2, 5]第二步处理下标 2 的节点值为 3。左孩子下标 5 值为 8右孩子下标 6 值为 2。8 最大交换[4, 10, 8, 9, 1, 3, 2, 5]第三步处理下标 1 的节点值为 10。左孩子下标 3 值为 9右孩子下标 4 值为 110 已经最大不动。第四步处理下标 0 的节点值为 4。左孩子下标 1 值为 10右孩子下标 2 值为 8。10 最大交换 4 和 10[10, 4, 8, 9, 1, 3, 2, 5]这里heapify递归继续检查下标 1 的位置。下标 1 现在的值是 4它的孩子是下标 3 的 9 和下标 4 的 1。9 最大交换[10, 9, 8, 4, 1, 3, 2, 5]然后继续检查下标 3 的位置值为 4它的孩子是下标 7 的 5。5 更大交换[10, 9, 8, 5, 1, 3, 2, 4]最终我们得到了一个合法最大堆[10, 9, 8, 5, 1, 3, 2, 4]。堆顶 10 是最大值并且每个父节点都不小于它的孩子。这个演示也解释了为什么建堆的时候要“从后往前”每处理一个节点它的子树已经是可靠的基础剩下的问题只是把当前节点“插”到合适位置。4. 排序阶段交换堆顶、缩小范围、再下沉4.1 排序循环里发生的三件事建堆完成后最大值在数组的开头。要得到升序数组还需要一个排序阶段。这个阶段做的事情非常机械把堆顶元素和数组当前末尾元素交换。因为堆顶是当前最大值交换后最大值就“定居”在末尾。把堆的有效范围缩小一个位置忽略已经排好的末尾元素。对新堆顶执行heapify把剩下的元素重新调整成最大堆。重复这三步直到堆的范围只剩一个元素。这里的关键点是每次交换完最大的元素就再也不用动了。堆的有效长度从n缩到n-1、n-2……直到 1。整个数组从后往前逐渐变成有序升序。正因为是在同一个数组里原地操作堆排序的空间复杂度是 O(1)。对应代码for i in range(n - 1, 0, -1): arr[i], arr[0] arr[0], arr[i] heapify(arr, i, 0)注意heapify的第二个参数传的是i而不是n。它的含义是“当前堆的有效长度”。交换之后下标i位置的元素已经被永久放置在最终位置不能再参与调整。4.2 用手工走一遍关键轮次继续用上面的堆[10, 9, 8, 5, 1, 3, 2, 4]做演示。第 1 轮i7。交换arr[0]10和arr[7]4[4, 9, 8, 5, 1, 3, 2, 10]现在 10 已经归位。对前 7 个元素执行heapify下标 0 的 4 和左孩子 9、右孩子 8 比9 最大交换。继续处理下标 1 的 4它的孩子是下标 3 的 5 和下标 4 的 15 最大交换。结果[9, 5, 8, 4, 1, 3, 2, 10]第 2 轮i6。交换堆顶 9 和末尾元素 2[2, 5, 8, 4, 1, 3, 9, 10]对前 6 个元素执行heapify下标 0 的 2 和孩子 5、8 比8 最大交换。继续处理下标 2 的 2它的孩子是下标 5 的 33 更大交换。结果[8, 5, 3, 4, 1, 2, 9, 10]能看到规律每轮结束后数组末尾都会多一个“已经排好的最大值”。继续这个过程到只剩一个元素整个数组就会变成升序。4.3 完整的堆排序代码把上面的建堆和排序阶段合起来就是一个完整的降序版堆排序等一下前面这个版本用的是最大堆排序结果是升序。完整代码如下def heapify(arr, n, i): largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left 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[i], arr[0] arr[0], arr[i] heapify(arr, i, 0)如果原数组[4, 10, 3, 5, 1, 8, 2, 9]经过heap_sort结果会是[1, 2, 3, 4, 5, 8, 9, 10]。有几个使用细节值得注意heap_sort是原地排序会直接修改传入的数组。如果你需要保留原数组调用前先arr.copy()。这个版本的实现用的是最大堆输出升序。如果你想要降序可以改用最小堆或者更简单的方式在比较上取反逻辑。构建堆的循环起点写成n // 2 - 1是最准确的。写n // 2甚至n // 2 1也不会报错因为那些下标的节点是叶子heapify会直接返回只是多做了一些无用功。5. 堆排序的真实代价复杂度、稳定性与缓存5.1 时间复杂度和空间复杂度怎么算出来的堆排序的时间复杂度有两个部分建堆阶段和排序阶段。建堆阶段很多人凭感觉认为复杂度是 O(n log n)因为每个节点都要进行调整。但实际上完整的数学推导结果是 O(n)。直觉是这样的堆的不同层节点数量不一样。越靠近底层的节点数量越多但它们下沉的路径短越靠近顶层的节点数量越少但它们下沉的路径长。把每一层的调整代价加总最后会收敛到一个线性复杂度而不是 n 个节点乘以 log n 的深度。排序阶段则很简单每次取堆顶并调整需要 O(log n)一共取 n-1 次所以是 O(n log n)。总复杂度就是 O(n log n)。关键是这个复杂度与输入数据的初始顺序无关。快速排序在最好情况下是 O(n log n)遇到特定输入可能退化到 O(n²)归并排序无论什么情况都是 O(n log n)但要额外 O(n) 空间。堆排序则是“最坏、最好、平均”都是 O(n log n)且属于原地排序。空间复杂度方面不考虑递归调用栈堆排序只使用常数级额外空间O(1)。如果算递归深度heapify的递归深度是树高 O(log n)但也仅此而已。一般我们把堆排序归类为原地排序算法。5.2 为什么它不是稳定排序稳定性指的是两个相等的元素排序后能不能保持原来的相对顺序。堆排序是不稳定的。原因在于堆内部的调整方式和“堆顶与末尾元素交换”的阶段。举个简单例子数组[3a, 3b, 1]下标 0 是 3a下标 1 是 3b下标 2 是 1。建堆阶段3a 和 3b 相等heapify中用的是“严格大于”才交换所以不会交换它们堆还是[3a, 3b, 1]。排序阶段第一轮交换堆顶 3a 和末尾元素 1[1, 3b, 3a]两个 3 的相对位置反了。原来 3a 在前现在 3a 跑到了 3b 后面。稳定排序的要求是相等元素排序后仍保持原顺序这里明显不满足。这个不稳定性的根源在于堆排序需要把堆顶元素“甩”到数组末尾这个操作会跨越中间一堆元素完全可能改变相等元素的相对顺序。如果你需要稳定排序堆排序不是一个合适的选择归并排序是更稳妥的答案。5.3 缓存不友好堆排序最容易忽略的短板看复杂度的表格堆排序的时间复杂度很优秀但很多实际测试里它的表现并不如快速排序原因除了常数项之外还有一个现代计算机体系结构的问题缓存命中率。数组在内存中是连续存储的。快速排序倾向于对整个数组进行分段扫描访问模式是连续的能充分发挥 CPU 缓存预取的优势。归并排序虽然需要额外空间但它读写数组也是相对连续的。堆排序不一样。它在调整堆的时候访问的下标是i、2*i1、2*i2父子节点在数组中相隔会越来越大。对于小数组这无所谓但数据量一大这种“跳跃式”访问就非常容易造成缓存未命中。这也就是常说的“常数项大”。它隐藏在大 O 复杂度里实际表现却实实在在地影响运行时间。这也是为什么语言内置的通用排序算法很少选用纯堆排序的原因。它们往往选择快速排序再用堆排序兜底最坏情况。6. 实操心得写堆排序容易踩的坑6.1 下标和边界0-based 下的判断技巧堆排序的递归实现里最容易写错的就是边界判断。严格来说每次都比较一下left n或right n是否成立。我见过很多初学者直接在代码里写if arr[2 * i 1] arr[largest]: ...这在2*i1超出数组长度时直接越界程序崩溃。正确的写法永远是先判断下标范围再比较值。尤其注意右孩子不是每个节点都有右孩子。另外还要小心建堆起点的计算。在 0-based 数组里最后一个非叶子节点是n // 2 - 1。有些资料用的是 1-based 下标描述算法转换到 0-based 代码时需要同时调整孩子下标和父节点下标公式。如果没转对三个下标全乱写出来的代码会非常诡异。6.2 递归版与迭代版 heapify 的选择heapify用递归写起来很简洁而且它的递归深度是二叉堆的高度 O(log n)对于常规数据规模完全不会触发栈溢出。但在性能要求严格的时候递归调用本身有开销。我在工程上更习惯用迭代版本def heapify(arr, n, i): while True: largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest i: break arr[i], arr[largest] arr[largest], arr[i] i largest这个版本把递归改成了循环逻辑完全一致但避免了函数调用的开销。这两种写法在思路上没有区别只是执行方式不同。6.3 什么时候别自己写堆排序写代码这么多年我的原则是能用内置库就用内置库。Python 有heapqJava 有PriorityQueueC 有priority_queue。这些库是被大量项目验证过的性能和边界都比自己写的更可靠。尤其是你把数据插入、弹出一堆操作混在一起的时候手写堆容易出现各种细小的下标错误排查起来很痛苦。需要自己实现堆排序或者堆的场景基本是这三种算法面试或考试要求手写堆排序。需要对底层比较逻辑做深度定制内置堆不能满足。比如要维护一个“取最小值但带有权重等额外条件”的复杂结构。平台或运行环境不允许使用标准库的某些容器。还有一个小技巧Python 的heapq只实现了最小堆。如果你想要最大堆最简单的办法是把所有元素取负数放进去。这个技巧在刷题和业务代码里都特别好用。我看过很多人写排序代码时明明只是要从一批数据里反复取最大值却用sort把整个数组反复排序。这本质上是对复杂度的认识不够。理解了堆排序之后你会自然地在脑子里多装一个工具遇到“动态极值”类问题优先想到堆遇到“把一个数组整理成完全有序”这种真正排序问题再去考虑快排、归并或者内置的sort。这才是堆排序留给我们最有价值的东西。