堆排序全解：从O(n)建堆到TopK与优先队列实战

堆排序这个算法，我前后在不同的项目里手写过不下五遍，每一次都以为自己已经吃透了，每一次又都能在某个下标或者循环边界上栽个跟头。很多人对它的印象停留在“面试常考、O(n log n)、不稳定”这三句话上，真要落到代码里，建堆为什么能做到线性时间、下沉和上浮到底该在哪个场景用哪一个、TopK 问题里为什么小顶堆反而存的是最大的那 K 个，这些问题一旦追问下去，能答利索的人并不多。这篇文章我打算把堆排序从数据结构形态、原子操作、复杂度推导、完整实现到真实业务里的四种用法，一路拆到底，中间穿插我自己调试时踩过的坑。适合已经会写冒泡和快排、想把堆这一块彻底打通的人，也适合平时用着语言自带的优先队列、但想知道底下到底发生了什么的开发者。看完至少能做到两件事：不看任何参考手写出正确的堆排序，以及在遇到“海量数据取前 K 个”这类需求时，第一时间想到该建大顶堆还是小顶堆。

1. 为什么我把堆排序单独拎出来讲：一次选型现场的复盘

1.1 三个候选方案的硬指标对比

前阵子处理一个日志聚合的模块，需要对一批百万级别的记录做排序，同时内存卡得很死，跑在一个资源受限的容器里，堆内存只给了很小的额度。当时摆在面前的就三个选项：快排、归并、堆排。这三个东西在教科书上的复杂度看起来差不多，但工程上的表现差异很大，我列了一张表来对比它们的真实特征。

决定性的因素是那一列“额外空间”。归并排序需要一个和原数组等长的辅助数组，百万条记录乘上单条记录的字节数，在内存紧张的环境里直接出局。快排空间上没问题，但它的最坏情况是 O(n²)，而这批日志的原始顺序有很强的规律性——大量记录的时间戳是单调递增的，快排在某些划分策略下退化得非常难看，虽然可以用随机化或者三数取中来缓解，但我不想在这种基础模块里赌概率。

堆排序把这两点都堵死了：原地排序，空间 O(1)；最坏情况也稳稳压在 O(n log n)。它的代价是缓存不友好，实际跑起来常数比快排大不少，但在这个场景里，稳定性比那点常数重要得多。

1.2 堆排序真正的主场在哪里

我得说句实话，纯粹的“把整个数组排好序”这个需求，堆排序在工程里用得并不多。语言标准库里的排序基本都是混合策略——小数组用插入排序，大数组用快排加堆排兜底，比如有些实现会在递归深度超过阈值时切到堆排序，就是为了防住快排退化的最坏情况。所以堆排序的第一重身份是“兜底保底方案”，它保证了一个上界。

它真正的第二重身份，是优先队列的底层结构。这个才是重点。堆排序这个算法本身，某种程度上是堆这种数据结构的副产品：你把一个大顶堆反复弹出堆顶放到数组末尾，最后得到的就是一个升序数组。理解了这句话，就理解了堆排序的全部流程。而堆作为独立的数据结构，在任务调度、流式统计、图算法（比如某类路径搜索里的取最小边）、事件驱动模拟这些地方，出镜率高得吓人。

所以我给的建议是：别把堆排序当成一个孤立的排序算法去背，把它当成“堆这个数据结构的一次完整消费过程”来理解。你先得知道堆怎么维护，排序只是顺带的结论。后面几节我基本就按这个思路走，先把结构讲透，再谈排序。

2. 一棵树如何塞进数组：堆的物理结构与下标映射

2.1 完全二叉树的数组表示

堆在逻辑上是一棵完全二叉树，注意“完全”这两个字，它约束了树的形状：除了最后一层，其他层必须填满；最后一层的节点必须从左到右连续排列，中间不能有空洞。这个约束看起来只是形状上的规矩，实际是整个堆能用数组存下来的根本原因。

因为形状规整，节点的位置就可以直接算出来，不需要任何指针。数组下标为i的节点，它的左孩子固定在2i + 1，右孩子固定在2i + 2，父节点固定在(i - 1) / 2（向下取整）。这三条公式就是堆的全部“寻址系统”。你想想如果换成一般的二叉树，左孩子可能空着、右孩子可能有值，那必须用指针或者额外的标记位，光是存储开销就翻倍了。

用数组存堆还有一层隐含好处：内存是连续的。虽然堆的访问模式是跳跃的（父节点和子节点下标差了将近一倍），但至少整个结构在一块连续内存里，对 GC 友好，序列化也方便——直接把数组扔过去就完事了，不用做树的遍历。

2.2 父子下标的推导与代码封装

那三条公式很多人是死记的，其实推导很简单。假设根节点下标是 0，第 1 层（根）有 1 个节点，第 2 层有 2 个，第 3 层有 4 个，第 k 层有 2^(k-1) 个。那么第 k 层第一个节点的下标，就是前 k-1 层节点总数，即 2^(k-1) - 1。站在下标i这个节点往上看，它所在的层里，它前面有若干个兄弟，这些信息凑一凑就能推出父节点是(i-1)//2。左孩子是2i+1这个更直接：下标i之前的所有层加起来是i个节点（因为完全二叉树按层序填），下一层的起点就是2i+1。

实际写代码的时候我习惯封装成几个小函数，避免在循环体里反复写这些表达式，一旦写错位置排查起来很痛苦。

def left_child(i): return 2 * i + 1 def right_child(i): return 2 * i + 2 def parent(i): return (i - 1) // 2

Python 里//是向下取整，正好符合需求。如果你用 Java 或 C 系语言，(i-1)/2对非负整数也是向下取整，没问题。但这里有个隐藏的坑：当i = 0时，parent(0)算出来是-1，某些语言里(0-1)/2是0（向零取整），这个差异会导致上浮操作死循环。所以上浮的循环条件一定要写成while i > 0而不是while parent(i) >= 0，靠条件本身挡住根节点，别指望公式能兜住。

2.3 大顶堆与小顶堆只差一个比较符

堆的性质只有一条：任意节点的值都不小于（或不大于）它所有子孙节点的值。注意这里说的是子孙，不是仅仅两个孩子。因为这条性质在每个节点上都成立，传递下来就保证了根节点是全堆的最大值（大顶堆）或最小值（小顶堆）。

大顶堆和小顶堆在实现上唯一的区别就是比较方向。写代码的时候我建议用一个统一的compare抽象，或者干脆把比较符抽成一个常量，避免出现“建堆时用大于号、下沉时用小于号”这种前后不一致的低级错误。这种错误特别隐蔽，因为代码能跑，结果只是错的，不报异常。

我一般的做法是：永远只实现大顶堆，需要小顶堆的时候把元素取相反数塞进去。取负是最省事的技巧，代价是数值范围的问题（如果元素是极小值附近可能溢出，但一般业务数据不会）。另一种做法是把比较器作为参数传进去，稍微啰嗦但是更通用。Python 的heapq模块就是只提供小顶堆，想用大顶堆就是存负数，你在看别人的代码时看到一堆负号别觉得奇怪，那是在模拟大顶堆。

3. 下沉与上浮：堆维护的两个原子动作

3.1 siftDown 的每一步在干什么

堆的所有操作，归根结底只有两个动作：下沉和上浮。这两个动作的作用都是“修复被破坏的堆性质”，区别在于破坏发生在哪个方向。

下沉（siftDown）处理的是“某个节点的值变小了”或者“某个节点的值比它的孩子小”这种情况。做法是把当前节点和它的两个孩子比一比，如果某个孩子比它大，就把两者交换，然后继续从新的位置往下走，直到要么没有孩子，要么两个孩子都不比它大。

这里有个关键细节：必须和两个孩子中较大的那个交换。如果你跟较小的那个换了，换完之后较大的那个孩子还是比新上来的父节点大，性质依然被破坏，你得多走一遍。跟大的换，一次就能保证交换后的父节点不小于另一个孩子，因为另一个孩子本来就不大于较大的那个。

def sift_down(arr, i, n): while True: left = 2 * i + 1 right = 2 * i + 2 largest = i 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

注意n这个参数。它表示“当前有效堆的范围”。在堆排序的过程中，堆的尾部元素一个个被摘出去放到数组末尾，堆的规模在缩小，所以每次下沉都要带一个上界。这个参数如果忘了传，或者传成了数组全长，排序结果会完全错乱，而且不会报错——这是我第一次手写堆排序时犯的错，调了快一个小时才反应过来。

3.2 siftUp 与它的适用边界

上浮（siftUp）处理的是相反的情况：新元素加到堆的末尾，它的值比父节点大，需要一路往上顶。做法很简单，跟父节点比，比父节点大就交换，然后继续往上。

def sift_up(arr, i): while i > 0: p = (i - 1) // 2 if arr[p] >= arr[i]: break arr[p], arr[i] = arr[i], arr[p] i = p

上浮的典型使用场景是往已有的堆里插入新元素。把新元素放到数组末尾，然后对它做一次上浮，堆性质恢复，复杂度 O(log n)。这也是优先队列push操作的标准实现。

那什么时候用下沉、什么时候用上浮？我的经验是看“破坏源在哪”。如果破坏源在堆顶（比如你把堆顶换成了一个很小的值，或者弹出堆顶后把末尾元素挪到堆顶），用下沉。如果破坏源在堆底（新插入元素），用上浮。建堆的时候用的是下沉，而且是从最后一个非叶子节点开始往前，这个后面单独讲为什么。

还有一个实际选择上的考量：下沉的过程中每次要比较两个孩子，上浮只比较一个父节点。所以单次下沉的常数开销比上浮略大。但建堆用下沉能做到 O(n)，用上浮是 O(n log n)，这个差距远大于那点常数，所以建堆一律用下沉。

3.3 手写时最容易错的三处

第一处是孩子的越界判断。左孩子下标的判断left < n很多人都记得，但右孩子的判断经常写成right < n之外的东西，或者忘记判断。如果右孩子越界了还去访问arr[right]，Python 直接抛 IndexError，还算幸运；C 系语言就是读越界内存，可能不崩但结果诡异。

第二处是交换后的下标更新。交换完必须把i更新成largest，然后继续循环。如果写成更新成left或者right，在某些情况下会走错分支。我见过一个写法是把交换和更新拆开写，结果中间插了一句break，导致只交换了一次就退出了。

第三处是循环终止条件。最常见的错法是写成while left < n，这个条件在孩子越界时确实会退出，但漏掉了“当前节点已经比两个孩子都大”这个退出条件。少了这个判断，循环会一直往下走到叶子然后靠越界退出，结果本身是对的（因为多余的交换不会发生，largest == i时不会交换），但多跑了无谓的层数。更糟的写法是while True但忘记在里面break，直接死循环。

4. 建堆为什么只要 O(n)：一个反直觉的复杂度推导

4.1 从最后一个非叶子节点开始的完整流程

建堆的过程就一行循环：

def build_heap(arr): n = len(arr) for i in range(n // 2 - 1, -1, -1): sift_down(arr, i, n)

起点是n // 2 - 1，也就是最后一个非叶子节点。为什么从这里开始？因为叶子节点没有孩子，天然满足堆性质，不需要调整。在完全二叉树里，下标大于等于n // 2的节点全是叶子。

然后倒着往前遍历，每个节点做一次下沉。倒序的意义在于：当你处理下标i的节点时，它的两个子树（下标 2i+1 和 2i+2）已经各自是合法的堆了，所以你只需要修复i这一个位置，下沉一次就能让整棵以i为根的树变成合法堆。这个顺序如果反了，从前往后处理，那下沉的时候子树还不是堆，做了也白做。

这个“自底向上、逐层合并”的思路其实在很多算法里都有，本质上是分治——把两个合法的堆合并成一个，只需要处理根节点。

4.2 节点高度求和法的直觉解释

这里是重点。很多人第一反应是：每个节点下沉一次，最坏情况下沉到叶子，高度是 log n，一共 n 个节点，那不就是 O(n log n) 吗？

这个估算错在把每个节点的高度当成了树的总高度。实际上绝大多数节点根本不在树的顶层，它们的高度很小。我来算一笔账。

假设树的高度是 h（根节点的高度记为 h，叶子记为 0，那么 h ≈ log₂n）。高度为 k 的节点最多有多少个？答：最多 2^(h-k) 个。这部分节点下沉的最远距离是 k 层。

总工作量 ≈ Σ（从 k=0 到 h）k × 2^(h-k)。

把公因子 2^h 提出来：2^h × Σ k / 2^k。后面这个级数从 1 到无穷的和是 2（这是个收敛级数，因为 k 的增长跟不上 2^k）。所以总工作量约等于 2 × 2^h，而 2^h ≈ n，所以总体是 O(n)。

用大白话说：树里约一半的节点是叶子，高度 0，代价为零；约四分之一是高度 1 的，每只下沉一步；约八分之一高度 2，下沉两步……节点数量按指数衰减，而代价只按线性增长，累加起来就被指数衰减主导了。真正贵的只有根节点一个，下沉 log n 步，但那只是一份 log n，不是 n 份。

我做过一个不太严谨但很有说服力的验证：n = 1024 的时候，理论总下沉步数大约是 2048 这个量级，而 n 个节点全部下沉 log n 步的估算会给出 10240，差了五倍。数据量越大差距越夸张。

4.3 逐条插入建堆为什么达不到 O(n)

对照着看，你就能明白为什么“一个个 push 进堆”的方式是 O(n log n)。逐个插入时，每个新元素都从堆底往上浮，第 i 个元素的平均上浮距离是 log i 步。累加起来是 Σ log i ≈ n log n。这里面大部分元素都是从最底层开始上浮的，代价一致地高，没有“指数衰减”带来的红利。

这两种建堆方式我在一个测试里对比过，处理 100 万条随机整数：

差距不算特别巨大，因为 log n 在 n = 10^6 时也只有 20。但如果这个建堆操作在一个高频调用的路径上，这接近一倍的差距就很可观了。另外注意，逐个插入的方式还需要额外的扩容操作（数组满了要扩容），实际开销还要再高一点。

5. 堆排序全流程实现与逐行注释

5.1 排序主循环的逻辑

建堆完成之后，arr[0]就是全数组的最大值。堆排序的核心动作就是：把堆顶和当前堆的最后一个元素交换，然后把堆的有效范围缩小一个，再对新的堆顶执行一次下沉。

def heap_sort(arr): n = len(arr) # 第一步：原地建堆，O(n) for i in range(n // 2 - 1, -1, -1): sift_down(arr, i, n) # 第二步：反复取堆顶放到末尾 for end in range(n - 1, 0, -1): arr[0], arr[end] = arr[end], arr[0] sift_down(arr, 0, end) return arr

交换之后，arr[end]位置上是当前最大值，这个位置从此固定不再动。有效堆的范围变成[0, end)，新堆顶是原来末尾那个元素，它大概率比孩子小，所以要做一次下沉把它放到合适的位置。重复这个过程，最大值从右往左依次就位，最后整个数组升序。

这里最容易搞混的是：大顶堆排序出来是升序。有人觉得大顶堆的最大值在顶上，怎么排出升序？因为最大值被放到了数组末尾啊。这个“放到末尾”的动作就是关键。

5.2 边界处理与循环不变式

那个for end in range(n - 1, 0, -1)的终止值是 0，不是 -1，也不是 1。这几种写法的差别值得抠一下。

当end = 1时，循环体做的是交换arr[0]和arr[1]，然后对范围[0, 1)下沉。范围里只有一个元素，下沉什么也不做。此时前两个元素已经有序，整个数组就有序了。如果写成range(n-1, -1, -1)，end = 0时会执行arr[0]和arr[0]的交换，无害但是无意义，同时sift_down(arr, 0, 0)会立刻因为孩子越界退出，也无害。所以两种写法结果一样，只是多跑一次空转。我倾向于写0作为终点，语义上更清楚。

循环不变式可以这样描述：在第k轮循环开始时，arr[end+1:]部分已经按升序排好，并且包含整个数组中最大的那些元素；arr[:end+1]部分仍然是一个合法的大顶堆。这个不变式是验证实现正确性的关键，你可以逐轮检验它是否成立。

还有一种实现是在数组开头加一个哨兵位（下标 0 空着，从 1 开始存数据），这样父子下标的公式变成2i和2i+1，少了一次加法和一次减法。这个技巧在 C 语言的老代码里很常见，现代语言里意义不大，反而要多占一个位置，我不推荐。但在某些对常数极其敏感的嵌入式场景里，确实有人这么做。

5.3 稳定性与工程取舍

堆排序是不稳定的。原因很直接：堆顶和末尾元素交换的时候，末尾那个元素可能和前面某个相等的元素交换了相对顺序，而且这个交换是跨越整个数组的，中间所有同值元素的相对位置都可能被打乱。

举个具体的例子，数组[2a, 2b, 1]（a、b 只是标记两个值相同的元素）。建堆后变成[2a, 2b, 1]（已经是大顶堆），第一轮交换arr[0]和arr[2]，得到[1, 2b, 2a]，然后下沉，最终结果[1, 2b, 2a]。原来 2a 在前 2b 在后，现在反了。

什么时候需要在意稳定性？当元素是复合对象、且你之后还要按另一个字段做二次排序的时候。比如先按时间排序，再按优先级排序，如果第二次排序不稳定，同优先级的元素时间顺序就乱了。这种场景要么用归并排序，要么给比较器加上次级比较键，别指望堆排序能保持顺序。

至于工程取舍，我的判断标准是这样的：如果数据量小于几千，直接用语言内置的排序，别折腾；如果数据量大且内存紧张，用堆排序；如果数据量大但内存充足、且对实际耗时敏感，用归并或者内置排序（内置排序通常是混合策略，实际表现最好）；如果是流式数据、随时可能来新元素、随时要取最大值，那才轮到堆作为数据结构上场。

6. 四个真实场景下的堆应用拆解

6.1 流式 TopK：大顶堆还是小顶堆，这个问题问倒过不少人

“从 1 亿个数里找最大的 100 个”，这是堆最经典的考题。正确做法是维护一个大小为 K 的小顶堆，很多人第一反应是建大顶堆，方向搞反了。

为什么是小顶堆？因为小顶堆的堆顶是这 K 个元素里最小的那个，也就是“当前入围者里最差的一个”。来了一个新元素，你只需要拿它跟堆顶比一下，比堆顶大就替换掉堆顶，然后下沉调整。整个过程只需要 O(log K) 的时间，内存只需要 O(K)。如果用大顶堆，堆顶是最大的，你没法快速判断新元素该不该进来。

import heapq def top_k(nums, k): if k <= 0: return [] heap = [] for x in nums: if len(heap) < k: heapq.heappush(heap, x) elif x > heap[0]: heapq.heapreplace(heap, x) return sorted(heap, reverse=True)

Python 的heapq是小顶堆，直接拿来用正好。注意heapreplace比先heappop再heappush快，它只做一次下沉，减少了函数调用和一次上浮。

这个方案比“全排完再取前 K”强在哪？全排是 O(n log n)，TopK 是 O(n log K)。K = 100、n = 10^8 的时候，log K 约等于 7，log n 约等于 27，差了将近四倍。更关键的是内存，全排要么外部排序要么把数据全读进内存，TopK 只需要 K 个位置。

我踩过的一个坑是：K 等于 0 或者 K 大于数组长度时的处理。K 为 0 时heap[0]会直接抛异常，得提前判断。K 大于数组长度时，前面的len(heap) < k分支会一直走，最后整个数组都被塞进堆里，功能上也对，但语义上应该理解为“全部数据”。这类边界在接口设计时就要想清楚。

6.2 任务调度里的优先队列

这个场景在后台服务里太常见了。一批任务有各自的优先级和到期时间，需要一个调度器每次取出“最该执行的那个”。如果每次取都遍历一遍找最大，复杂度 O(n)，任务一多就顶不住。

用堆实现优先队列，取和插都是 O(log n)。而且堆只保证堆顶是最值，不保证整体有序，这个“部分有序”恰好就是调度器需要的——它从来不需要看全部任务的完整顺序，只需要知道下一个是谁。

import java.util.PriorityQueue; class Task implements Comparable<Task> { String id; int priority; long deadline; Task(String id, int priority, long deadline) { this.id = id; this.priority = priority; this.deadline = deadline; } @Override public int compareTo(Task o) { if (this.priority != o.priority) { return Integer.compare(o.priority, this.priority); } return Long.compare(this.deadline, o.deadline); } } PriorityQueue<Task> queue = new PriorityQueue<>();

这里有两个经验点。第一，比较器必须写全。只按优先级比较的话，同优先级的任务在堆里的相对顺序是不确定的，而且每次调整都可能变，调试的时候你会看到顺序莫名其妙地跳。加上 deadline 作为次级键，行为就稳定多了。第二，不要修改已经入堆的对象的比较字段。如果你把一个任务放进堆里之后又改了它的 priority，堆结构就被悄悄破坏了，后续操作全是错的。要改就先删再插，或者用“惰性删除”的思路，弹出来的时候检查一下是否已失效。

6.3 合并 K 个有序序列

这个需求在日志系统里很常见，多个分片各自按时间有序，要合并成一个全局有序流。最朴素的做法是每次从 K 个序列的头部找最小的，需要比较 K 次，总共 O(nK)。用堆维护 K 个头部元素，每次取最小的只需要 O(log K)，总体 O(n log K)。

import heapq def merge_k(lists): heap = [] for idx, lst in enumerate(lists): if lst: heapq.heappush(heap, (lst[0], idx, 0)) result = [] while heap: val, list_i, elem_j = heapq.heappop(heap) result.append(val) if elem_j + 1 < len(lists[list_i]): heapq.heappush(heap, (lists[list_i][elem_j + 1], list_i, elem_j + 1)) return result

元组里放(值, 列表编号, 元素下标)这个三元组，是因为当两个值相等时，Python 会去比较第二个元素。如果第二个也是列表，就会报“列表之间不能比较”的错误。塞一个整数编号进去，就保证比较永远有结果。这个细节我第一次写的时候完全没意识到，本地测试数据恰好没有重复值，一上真实数据就炸了。

还有个优化思路：如果 K 比较大，可以先对 K 个头部建堆，然后每次弹出后插入新的头部，这才是真正意义上的“利用堆”。上面那个写法已经是在用堆了，但如果 K 是百万级，heappush一个个调用的开销也不小，可以先用heapify一次性建堆。

6.4 双堆维护动态中位数

数据流的中位数，这个问题的解法特别巧妙，值得单独说一下。思路是维护两个堆：一个大顶堆存较小的一半，一个小顶堆存较大的一半。两个堆的大小差不超过 1，那么中位数要么是大顶堆的堆顶（当总数为奇数），要么是两个堆顶的平均值。

import heapq class MedianFinder: def __init__(self): self.small = [] # 大顶堆，存负数 self.large = [] # 小顶堆 def add(self, num): heapq.heappush(self.small, -num) heapq.heappush(self.large, -heapq.heappop(self.small)) if len(self.large) > len(self.small): heapq.heappush(self.small, -heapq.heappop(self.large)) def median(self): if len(self.small) > len(self.large): return -self.small[0] return (-self.small[0] + self.large[0]) / 2

插入逻辑是三步走：先无条件塞进大顶堆，再把大顶堆的最大值挪到小顶堆，最后如果小顶堆比大顶堆多了，再把小顶堆的最小值挪回来。这个“先塞再平衡”的写法比“判断该进哪边再平衡”要简洁得多，也不会出错。

这里small堆存的是负数，因为 Python 没有内置大顶堆。取中位数的时候要取反回来，这个正负号很容易看漏。我第一次写的时候median里忘了取反，返回的是个负数，还纳闷了半天。

7. 调试实录：几个把我卡住半小时以上的坑

7.1 下标越界与循环终止条件

最典型的一次：写sift_down的时候，孩子越界判断写成了left <= n而不是left < n。这个=号的差别导致访问了数组外的位置。在 Python 里这直接抛 IndexError，堆栈指向下沉函数内部，但你得往前翻才能发现是边界条件写错了。在 C 系语言里这个问题更阴险，读越界内存不崩，只是拿了个垃圾值参与比较，排序结果错得莫名其妙。

我现在写这段代码的习惯是：先在纸上把 n = 1、n = 2、n = 3 三种情况列出来，手动走一遍。n = 1 时建堆循环的起点是1//2 - 1 = -1，range 为空，直接跳过，排序循环range(0, 0, -1)也是空，数组原样返回，正确。n = 2 时建堆起点是2//2 - 1 = 0，对根做一次下沉，然后排序循环range(1, 0, -1)走一轮，交换arr[0]和arr[1]，下沉范围是 1，什么都不做，结束。这三种情况走通，基本就不会有边界问题了。

7.2 排序范围忘记收缩

另一个经典错误：排序主循环里调用sift_down(arr, 0, n)，把第三个参数写成了固定的n而不是end。代码能跑，数组也不越界，但结果完全错——因为已经排好的尾部元素又被卷进堆里了，导致下一轮取出的堆顶可能不是剩下的最大值。这种错误最难受，因为它不报错，只是结果不对，而且数据量小的时候看起来可能还有部分是排好的，很容易误判成“差不多对”。

我的应对方法是写一个断言：在每一轮循环结束后，检查arr[end:]这部分是否已经有序，且都大于等于arr[:end]。这个检查在生产代码里当然不能留，但在本地调试阶段花几行代码加上，能瞬间定位问题是否出在范围收缩上。

7.3 大小顶堆切换时的符号错误

从大顶堆改小顶堆的时候，要改的地方不止一处：比较方向要改，largest变量名该变成smallest，交换条件要改。但很多人只改了比较符，忘了改初始值的语义，或者改了一半。更隐蔽的是，在 Python 里用取负法模拟大顶堆时，如果某个地方忘了取负，就会出现“一部分按大顶堆比、一部分按小顶堆比”的混合状态，结果完全不可预测。

我的做法是彻底不写两套。要小顶堆就用heapq加负数，要自己实现就只实现一套，用比较函数参数化。宁可多传一个参数，也不要在两套几乎相同的代码里改来改去。复制粘贴改代码是 bug 的高发区，尤其是这种“只差一个符号”的情况。

8. 性能实测与使用建议

8.1 与快排、归并的实际耗时对比

我在一台普通开发机上跑了一组对比，数据是随机整数，重复跑了五次取中位数，只代表这个特定环境下的相对关系：

这张表里最有信息量的是最后一行。已经接近有序的输入是快排的噩梦，退化到 O(n²) 之后耗时直接翻了十倍以上。堆排序在这一行没什么变化，因为它对输入顺序完全不敏感，建堆阶段对有序数组甚至更快。内置排序因为有混合策略和提前检测有序的优化，表现依然最好。

堆排序在随机数据上的常数大概是快排的两到三倍，主要成本来自缓存不友好。每次下沉都要跳着访问2i+1和2i+2，内存访问的局部性很差，CPU 缓存命中率低。快排是顺序扫描，缓存命中率高得多。这个差距在大数据量下更明显，因为数据装不进 L2 缓存之后，内存墙的影响就出来了。

8.2 什么时候不该用堆

我得给堆泼点冷水，有些场景用堆是自找麻烦。

需要在有序数据里反复范围查询的时候，别用堆。堆只保证堆顶是最值，你没法高效地取第二小、第三小，也没法做范围扫描。这种场景用平衡树或者跳表更合适，虽然实现复杂，但接口匹配。

数据规模很小的时候，别用堆。数据量在几十个这个级别，插入排序的实际耗时往往比堆排序还低，因为常数小、缓存友好、没有复杂的分支。很多标准库的排序实现会在这个规模直接切到插入排序，就是这个道理。

只需要一次最大值、不需要反复取的时候，别用堆。遍历一遍找最大是 O(n)，建堆也是 O(n)，但建堆的常数大得多，纯属浪费。

需要稳定排序的时候，别用堆。前面说过原因了，这个没有补救办法，只能换算法。

元素比较的代价极高的时候，要慎重。堆排序的比较次数大约是 2n log n 次，比归并排序多。如果每次比较都很贵（比如字符串的字典序比较、复杂对象的深层比较），这个常数放大就很疼了。

8.3 一个实用的优化思路：只建一次堆，复用结构

如果你的场景是“反复取最大值，偶尔插入新元素”，那其实不需要每次取完都重新建堆。堆的结构在弹出堆顶后只需要一次下沉就能恢复，代价是 O(log n)。很多人写着写着变成了“每次取完都重新build_heap”，那是 O(n) 的开销，白白浪费了堆的价值。

还有一个思路是用heapify一次性建堆而不是逐个 push。Python 的heapq.heapify是原地的，复杂度 O(n)，如果你已经有一个列表要转成堆，永远优先用它而不是循环heappush。这个差别在构建大量元素的堆时非常明显。

最后分享一个我自己的小经验：调试堆相关代码的时候，别一上来就看最终结果对不对。先把堆的结构打印出来，或者写一个函数验证“每个节点都大于等于它的孩子”这个性质在整个数组上是否成立。这个检查逻辑只有几行，但能立刻区分“堆建错了”和“排序流程错了”这两类问题，能省下大量时间。堆的性质验证比结果对比更早地暴露问题，因为结果错可能是最后一步才错的，而结构错是更早埋下的雷。