堆排序这个算法我前后在不同的项目里手写过不下五遍每一次都以为自己已经吃透了每一次又都能在某个下标或者循环边界上栽个跟头。很多人对它的印象停留在“面试常考、O(n log n)、不稳定”这三句话上真要落到代码里建堆为什么能做到线性时间、下沉和上浮到底该在哪个场景用哪一个、TopK 问题里为什么小顶堆反而存的是最大的那 K 个这些问题一旦追问下去能答利索的人并不多。这篇文章我打算把堆排序从数据结构形态、原子操作、复杂度推导、完整实现到真实业务里的四种用法一路拆到底中间穿插我自己调试时踩过的坑。适合已经会写冒泡和快排、想把堆这一块彻底打通的人也适合平时用着语言自带的优先队列、但想知道底下到底发生了什么的开发者。看完至少能做到两件事不看任何参考手写出正确的堆排序以及在遇到“海量数据取前 K 个”这类需求时第一时间想到该建大顶堆还是小顶堆。1. 为什么我把堆排序单独拎出来讲一次选型现场的复盘1.1 三个候选方案的硬指标对比前阵子处理一个日志聚合的模块需要对一批百万级别的记录做排序同时内存卡得很死跑在一个资源受限的容器里堆内存只给了很小的额度。当时摆在面前的就三个选项快排、归并、堆排。这三个东西在教科书上的复杂度看起来差不多但工程上的表现差异很大我列了一张表来对比它们的真实特征。维度快速排序归并排序堆排序平均时间复杂度O(n log n)O(n log n)O(n log n)最坏时间复杂度O(n²)O(n log n)O(n log n)额外空间O(log n) 递归栈O(n) 辅助数组O(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。左孩子是2i1这个更直接下标i之前的所有层加起来是i个节点因为完全二叉树按层序填下一层的起点就是2i1。实际写代码的时候我习惯封装成几个小函数避免在循环体里反复写这些表达式一旦写错位置排查起来很痛苦。def left_child(i): return 2 * i 1 def right_child(i): return 2 * i 2 def parent(i): return (i - 1) // 2Python 里//是向下取整正好符合需求。如果你用 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的节点时它的两个子树下标 2i1 和 2i2已经各自是合法的堆了所以你只需要修复i这一个位置下沉一次就能让整棵以i为根的树变成合法堆。这个顺序如果反了从前往后处理那下沉的时候子树还不是堆做了也白做。这个“自底向上、逐层合并”的思路其实在很多算法里都有本质上是分治——把两个合法的堆合并成一个只需要处理根节点。4.2 节点高度求和法的直觉解释这里是重点。很多人第一反应是每个节点下沉一次最坏情况下沉到叶子高度是 log n一共 n 个节点那不就是 O(n log n) 吗这个估算错在把每个节点的高度当成了树的总高度。实际上绝大多数节点根本不在树的顶层它们的高度很小。我来算一笔账。假设树的高度是 h根节点的高度记为 h叶子记为 0那么 h ≈ log₂n。高度为 k 的节点最多有多少个答最多 2^(h-k) 个。这部分节点下沉的最远距离是 k 层。总工作量 ≈ Σ从 k0 到 hk × 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 万条随机整数建堆方式耗时相对值时间复杂度自底向上 siftDown1.0O(n)逐个 siftUp 插入1.8O(n log n)差距不算特别巨大因为 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[end1:]部分已经按升序排好并且包含整个数组中最大的那些元素arr[:end1]部分仍然是一个合法的大顶堆。这个不变式是验证实现正确性的关键你可以逐轮检验它是否成立。还有一种实现是在数组开头加一个哨兵位下标 0 空着从 1 开始存数据这样父子下标的公式变成2i和2i1少了一次加法和一次减法。这个技巧在 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, reverseTrue)Python 的heapq是小顶堆直接拿来用正好。注意heapreplace比先heappop再heappush快它只做一次下沉减少了函数调用和一次上浮。这个方案比“全排完再取前 K”强在哪全排是 O(n log n)TopK 是 O(n log K)。K 100、n 10^8 的时候log K 约等于 7log 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 ComparableTask { 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); } } PriorityQueueTask 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 -1range 为空直接跳过排序循环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 与快排、归并的实际耗时对比我在一台普通开发机上跑了一组对比数据是随机整数重复跑了五次取中位数只代表这个特定环境下的相对关系数据规模快速排序归并排序堆排序内置排序1 万1.01.21.90.810 万1.01.12.30.7100 万1.01.22.80.7100 万已近有序12.41.22.70.8这张表里最有信息量的是最后一行。已经接近有序的输入是快排的噩梦退化到 O(n²) 之后耗时直接翻了十倍以上。堆排序在这一行没什么变化因为它对输入顺序完全不敏感建堆阶段对有序数组甚至更快。内置排序因为有混合策略和提前检测有序的优化表现依然最好。堆排序在随机数据上的常数大概是快排的两到三倍主要成本来自缓存不友好。每次下沉都要跳着访问2i1和2i2内存访问的局部性很差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。这个差别在构建大量元素的堆时非常明显。最后分享一个我自己的小经验调试堆相关代码的时候别一上来就看最终结果对不对。先把堆的结构打印出来或者写一个函数验证“每个节点都大于等于它的孩子”这个性质在整个数组上是否成立。这个检查逻辑只有几行但能立刻区分“堆建错了”和“排序流程错了”这两类问题能省下大量时间。堆的性质验证比结果对比更早地暴露问题因为结果错可能是最后一步才错的而结构错是更早埋下的雷。