堆排序：从完全二叉树到优先队列与TopK的工程应用

堆排序在九大排序算法里一直是个特殊的存在：它不像冒泡、插入那样贴着“直观”二字，也不像快排那样靠着“分治”的名号被人熟知。很多人学它的时候，总卡在“堆到底是个啥”这个问题上，好不容易把建堆代码背下来了，过两周又忘得干干净净。这篇内容我把自己的理解方式、调试过的代码、踩过的坑一起整理出来，希望能帮你把堆排序真正变成那种“以后随时能徒手写出来”的算法。它适合算法刚入门的同学，也适合准备面试想系统梳理排序算法的人，哪怕你已经在用高级语言写业务代码，回头再看一遍堆的思想，对理解优先队列、TopK、定时器这些日常组件也有实打实的帮助。

1. 堆排序的核心思路：一个“值班队长”的选举机制

1.1 堆是什么：用数组存成一棵“偏心”的完全二叉树

老规矩，先解决概念。堆（Heap）不是内存里那个 malloc 出来的堆，它是一种数据结构，本质是一棵完全二叉树，只是这棵树有个额外规定：父节点的值要么大于等于所有子孙（大根堆），要么小于等于所有子孙（小根堆）。这个规定只约束父子之间的大小关系，不约束左右兄弟谁大谁小，所以它是一棵“偏心的树”，不需要完全有序。

为什么用数组就能存？因为完全二叉树本身是“紧凑”的，除了最后一层，其他层都是满的，最后一层节点也都靠左排列。这样我们就可以按下标把节点铺进数组：某个节点在数组下标 i，那它的左孩子就是 2i+1，右孩子是 2i+2，父节点是 (i-1)//2。这个下标关系是堆排序所有代码的基石，写的时候一旦算错，后面全部连锁出错。

我用一个生活中的类比帮你记：可以把堆想象成一个公司的值班领导序列。大根堆就是“领导永远比下属资历深”，每次你要给一个任务分配人，直接看数组第一个元素，它必然是当前资历最深的那个。堆排序干的事，就是把这个“值班序列”反复维护好，然后每次把最厉害的那个人“请出列”放到最终位置。

1.2 堆排序的两阶段流程：先建堆，再反复“摘顶”

堆排序整个过程就分两大阶段，非常清晰。

第一阶段是建堆。拿一个无序数组，通过从下往上的调整，把它变成一个大根堆（升序排序用大根堆）。建完之后，数组的第一个元素就是整个序列的最大值。

第二阶段是排序。把堆顶元素和当前堆的最后一个元素交换，此时最大值就到了数组末尾的正确位置。然后把堆的规模缩小一个，再把新的堆顶元素下沉到它该去的位置，重新维护成大根堆。接着再交换堆顶和新的最后一个元素……重复这个过程，直到堆里只剩一个元素。

这里有个新手特别容易搞混的点：升序排序为什么用大根堆而不是小根堆？因为大根堆把最大值“摘”出来放到数组尾部，越放到后面越大，自然就成了升序。要是用小根堆，你每次摘的是最小值，放到数组尾部就成了降序。想清楚这个方向，代码才不会写反。

1.3 复杂度与稳定性的真相：O(n log n)，但不是稳定排序

堆排序的时间复杂度是 O(n log n)，这一点无论最好、最坏还是平均情况都成立。空间复杂度是 O(1)，因为所有的交换都在原数组里完成，不借助额外数组。这也是它对比归并排序的一大优势——归并排序的空间复杂度是 O(n)，数据量大的时候内存开销不容忽视。

但堆排序有个硬伤：不稳定。所谓稳定，是指两个值相等的元素，排序后相对位置不变。堆排序在“摘顶”和“下沉”时，元素会进行跳跃式交换，一个元素可能从树顶一路沉到树底，这个过程中相等元素的先后顺序很可能被打破。后面我会专门给一个例子，让你直观看到它是怎么“翻车”的。

另外还要知道，虽然堆排序和快排都是 O(n log n)，但堆排序在随机数据上的常数因子比快排大，所以很多语言的内置排序并没有直接采用堆排序。这并不代表堆排序没用——它的价值更多体现在“只需要知道最大/最小的若干个元素”的场景里，也就是后面要讲的 TopK、优先队列这些地方。

2. 建堆过程拆解：从无序数组到合法大根堆

2.1 下沉操作：堆排序最核心的原语

堆排序几乎所有的复杂度都集中在一个操作上：下沉（sift down / heapify down）。给你一个父节点位置 i 和当前堆的边界 end，我们需要保证 i 以及它下面的整棵子树都满足大根堆性质。做法是：

1. 比较节点 i、左孩子、右孩子三个值，找出最大的那个的下标 largest。
2. 如果 largest 就是 i，说明父节点已经比两个孩子都大，结束。
3. 如果 largest 是某一个孩子，就把 i 和 largest 交换，然后让 i 指向 largest，继续重复这个过程，直到越界或不再需要交换。

注意，判断孩子是否越界是必须做的。左孩子存在不代表右孩子也存在，尤其当堆的规模是偶数时，最后一个非叶子节点可能只有左孩子。我在代码里见过的低级错误，十有八九是这里忘了判断右孩子是否在边界内。

下沉操作被我称为“单个节点的自我纠错”。它只负责让一个不合法的节点往下走，走到它该待的位置。建堆就是让所有非叶子节点都做一次下沉，排序阶段是每次交换后让新堆顶做一次下沉。整个堆排序的循环体里，本质上只有这一段在干活。

2.2 手动推演建堆全过程

光讲理论不好消化，我们拿一个具体数组手推一遍。假设数组是[4, 10, 3, 5, 1]，长度 n=5。要建大根堆，先找最后一个非叶子节点，下标是n//2 - 1 = 5//2 - 1 = 1，也就是值 10 的那个节点。

从下标 1 开始向前遍历：

第一步，处理下标 1（值 10）。它的左孩子是下标 3（值 5），右孩子是下标 4（值 1）。10 已经大于两个孩子，不需要操作。

第二步，处理下标 0（值 4）。它的左孩子是下标 1（值 10），右孩子是下标 2（值 3）。三个中最大的是 10，所以把 4 和 10 交换，数组变成[10, 4, 3, 5, 1]，当前要检查的位置变成下标 1。

下标 1 的值现在是 4，它的左孩子是下标 3（值 5），右孩子是下标 4（值 1）。最大值是 5，所以继续交换，数组变成[10, 5, 3, 4, 1]，位置来到下标 3。下标 3 的孩子下标是 7 和 8，都超出数组范围，检查结束。

到这里，建堆完成。最终数组[10, 5, 3, 4, 1]满足大根堆性质：10 大于 5 和 3，5 大于 4 和 1。注意这个数组并不是完全有序的，比如 3 是 10 的右孩子，但 4 和 1 都比它大。堆只保证父子关系，不保证兄弟关系，这是新手最容易误解的地方。

2.3 建堆复杂度为什么是 O(n)：反直觉但成立

很多人第一次看到建堆复杂度是 O(n) 都不信——毕竟要对 n/2 个节点各做一次下沉，而每次下沉最坏是 O(log n)，乘起来不应该是 O(n log n) 吗？问题在于，并不是每个节点都会下沉 O(log n) 次。

你想想，树的底部节点确实多，但它们离叶子近，下沉次数少；顶部节点下沉次数多，但顶部节点总共就那么几个。具体来说，树的高度是 h，从最底层往上数第 k 层的节点，最多只需要下沉 k 次。把这些工作量全部加起来，是一个收敛的几何级数，总和趋近于线性。

数学上可以这么理解：如果把所有非叶子节点的下沉次数加起来，大致等于每个节点乘以它所在的层高，这个求和最终会收敛到一个常数倍 n，也就是 O(n)。这个结论在《算法导论》里有严格证明，面试的时候能说出来“建堆是 O(n)”并且解释清楚“不是每个节点都下沉 O(log n) 次”，已经比大多数人强了。

3. 堆排序完整代码与过程推演

3.1 可直接运行的实现

我用 Python 写一个清晰版本，重点是让思路透明，方便你翻译成其他语言。

def sift_down(nums, start, end): # 大根堆下沉：让 start 位置的节点向下走到合适位置 # end 是当前堆的最后一个下标 i = start while True: left = 2 * i + 1 right = 2 * i + 2 largest = i if left <= end and nums[left] > nums[largest]: largest = left if right <= end and nums[right] > nums[largest]: largest = right if largest == i: break nums[i], nums[largest] = nums[largest], nums[i] i = largest def heap_sort(nums): n = len(nums) # 第一阶段：建堆，从最后一个非叶子节点往前逐个下沉 for i in range(n // 2 - 1, -1, -1): sift_down(nums, i, n - 1) # 第二阶段：反复把堆顶换到末尾，缩小堆范围再下沉 for end in range(n - 1, 0, -1): nums[0], nums[end] = nums[end], nums[0] sift_down(nums, 0, end - 1) return nums

这份代码直接把“建堆”和“排序”两个阶段分开了，handle里的边界条件也写得很明确。实际写代码的时候，很多人喜欢把 sift_down 写成递归，我个人建议先用循环写，因为循环不需要担心递归深度，调试起来也更容易定位。等彻底理解了，再改递归也不迟。

有一个小技巧：sift_down 的 end 参数是“当前堆最后一个元素的下标”，而不是堆的长度。排序阶段每轮把 end 减一，比传一个长度进去再在函数里减一更直观，也更容易避免 off-by-one 错误。

3.2 排序阶段一步一步推演

我们还用刚才那个建好的大根堆[10, 5, 3, 4, 1]来推演排序阶段。为了清楚，我标出每次操作后的数组状态。

初始大根堆：[10, 5, 3, 4, 1]

第一轮：交换堆顶和末尾，得到[1, 5, 3, 4, 10]，此时 10 已经固定。堆的范围缩小到前 4 个元素，然后对新的堆顶 1 做下沉。1 的孩子是 5 和 3，5 最大，交换后[5, 1, 3, 4, 10]；继续下沉，1 的孩子是 4，4 更大，交换得到[5, 4, 3, 1, 10]。堆又合法了。

第二轮：交换堆顶 5 和当前末尾 1，得到[1, 4, 3, 5, 10]，5 固定。堆范围缩到前 3 个元素。对堆顶 1 下沉，1 的孩子是 4 和 3，4 最大，交换得到[4, 1, 3, 5, 10]，继续检查位置 1，它没有合法孩子了，结束。

第三轮：交换堆顶 4 和末尾 3，得到[3, 1, 4, 5, 10]，4 固定。堆范围缩到前 2 个元素，对堆顶 3 下沉，它的孩子是 1，3 已经更大，不需要交换。

第四轮：交换堆顶 3 和末尾 1，得到[1, 3, 4, 5, 10]，3 固定。堆只剩一个元素，排序完成。

看这个过程，你会发现每一轮的操作模式完全一样：摘顶、把末尾换上来、下沉、缩小规模。这就是堆排序的节奏感。等你能在纸上独立把这个推演画完，代码基本不会写错。

3.3 边界条件与代码细节

有几个边界条件值得反复强调。

第一，建堆起点是n // 2 - 1。为什么？因为下标大于等于n // 2的节点都是叶子节点，叶子节点没有孩子，下沉操作什么都不用做。从最后一个非叶子节点开始往前处理，可以保证处理每个节点时，它的两个孩子都已经是合法堆，这样一次下沉就能让整棵子树合法。

第二，下沉过程中比较左右孩子时，不能直接用nums[left] > nums[right]来决定。因为右孩子可能根本不存在。正确做法是先假设父节点最大，然后分别和左右孩子比较，谁大谁替代 largest。这样可以自然地处理“只有左孩子”的情况，代码也更稳健。

第三，排序阶段的循环条件是end > 0，不是end >= 0。当只剩下一个元素时，它天然就在正确位置，不需要再操作。如果条件写错了，很容易出现访问负下标的问题。

4. 堆排序的工程应用：TopK、优先队列与变体

4.1 海量数据 TopK：小根堆的正确用法

堆排序在工程里最常见的“代言人”就是 TopK 问题：从海量数据里找最大的 K 个。直接全量排序的复杂度是 O(n log n)，如果数据量是几亿条，这成本太高。正确的思路是维护一个大小为 K 的小根堆。

怎么操作？先把前 K 个元素放进小根堆，此时堆顶是这 K 个元素里最小的。然后遍历剩余元素，每来一个，如果它比堆顶大，就替换堆顶并下沉；如果比堆顶小，直接跳过。遍历结束后，堆里的 K 个元素就是全局最大的 K 个，堆顶是第 K 大的数。

这个方案的时间复杂度是 O(n log K)，空间复杂度是 O(K)。当 K 远小于 n 时，效果非常明显。你可以把它理解成一个“淘汰机制”：小根堆的堆顶是当前候选人里最弱的，新人只有比最弱的强，才有资格入场。这和现实里的面试筛选逻辑一模一样。我实际处理过几百万条日志求 Top10 的需求，用这个方法几十毫秒就出结果，而直接排序会慢一个数量级。

4.2 优先队列与任务调度：堆才是主角

很多人没意识到，我们日常用的 PriorityQueue 底层就是堆，最常见的是二叉堆。操作系统里的定时器、调度器，网络框架里的延时任务，数据库里的排序归并，底层都会用堆来维护“下一个要执行的任务”。

拿一个小型定时器举例：你需要在一堆定时任务中，每次快速找到“最近到期”的那个。如果用普通数组，找到最小到期时间需要 O(n)，任务多时代价很大。换成小根堆，堆顶永远是最快到期的任务，取堆顶是 O(1)，插入和删除是 O(log n)。这就是为什么堆在实时系统里如此吃香——它不在于把全部数据排好序，而在于始终用最低成本维护“最小的在哪”。

从这个角度看，堆排序本身反而只是“顺带练手”的产物。真正值钱的是堆这种数据结构，以及围绕它的 Building、SiftDown、Pop、Push 这些操作。你一旦把堆排序的代码写明白了，优先队列、TopK、N 路归并这些问题的解法几乎是白送的。

4.3 堆的变体：d 叉堆、索引堆与堆排序的工程定位

二叉堆只是一个起点。D 叉堆让每个节点有 d 个孩子，d 更大时堆更“矮”，下沉时比较次数变多但层数变少，在缓存读取上也有差异，适合特定场景。索引堆则在节点上额外维护索引数组，使得你能快速定位某个元素在堆里的位置，解决“外部元素值变化后怎么高效更新堆”的问题，它是 Dijkstra 等图算法里常见的数据结构。

至于堆排序本身在工程整体排序里的定位，说实话有点“尴尬”。它虽然最坏情况稳定是 O(n log n)，但常数较大，且对内存的访问是跳跃式的——从树顶跳到树底，再跳到另一个分支，这对 CPU 缓存非常不友好。快速排序的访问模式是线性的，缓存命中率高，所以大多数语言的排序库都会优先快排。工程实践中更常见的做法是 Introspective Sort：以快排为主，但当递归深度过深时切到堆排序，防止恶意输入把快排退化到 O(n²)，同时还会在数据量小时切换成插入排序。堆在这里扮演的是“兜底”角色，而不是“主角”。

5. 堆排序常见问题与踩坑实录

5.1 稳定性：为什么相等元素会悄悄“翻车”

堆排序不稳定这件事，光记结论不够，最好理解它具体发生在哪一步。拿数组[3a, 3b, 1]（a、b 用来区分两个值相等的 3）为例。建堆时，如果左右孩子都等于父节点，我们可能选择交换其中一个，这本身就是一次位置变更。更典型的破坏发生在排序阶段：当堆顶被换到末尾时，原本在树深处的另一个相同值可能被“顶”上来。

例如大根堆里有两个相等的最大值，一个在堆顶，一个藏在子树中。第一轮摘顶，把堆顶那个放到末尾；第二轮继续下沉时，子树里那个相同值可能被换到堆顶，然后又放到末尾。这样两个相等元素的相对顺序就反了。有种说法是“堆排序可以通过某些技巧部分保持稳定性，但会牺牲性能或变成非原地”，工程上基本默认堆排序就是不稳定排序。面试问到这里，你只要能准确说出“元素发生跳跃式交换，相等元素相对顺序无法保证”就够了。

5.2 排查速查表：我遇到过的五种典型问题

我把自己平时调试堆排序时见过的问题整理成了一个小表，写代码的时候建议照着自查：

这些错误里，最常见的是第二种和第四种。特别是刚把递归版改成循环版的时候，特别容易忘更新 i，导致死循环。我的习惯是每写完一个排序函数，先用[5, 4, 3, 2, 1]、[1, 2, 3, 4, 5]、[3, 3, 3, 3]这几组特征数据分别跑一遍，能过这关再谈性能。

5.3 个人经验：什么时候我会选堆排序

最后分享一点实际工作中的选择心得。整体排序我只在极少数场景主动用堆排序，比如嵌入式环境里内存极紧张、没法开额外数组，或者数据流实时到来、必须增量维护并随时取最大最小时，我会用堆。

如果是“一次性把一个大数组完全排好序”，我更倾向用内置排序，因为实现经过了高度优化。如果题目明确要求“不能使用额外空间”，堆排序是 P0 候选。如果要求“保持稳定性”，则排除堆排序，考虑归并排序。如果只是求 Top 100，那无脑堆。把这些选择标准记在心里，你才算真正把排序算法从“面试题”变成了“工具箱”。

我个人的体会是，堆排序是那种“学的时候觉得绕，理解之后觉得太巧妙了”的算法。它的建堆 O(n) 是我当年第一次感受到数学分析在算法里的力量。建议你把这篇文章里的推演亲手画一遍，再动手写一遍代码，两遍之后，堆排基本就焊在脑子里了。之后再去看优先队列、TopK、堆优化的 Dijkstra，你会发现全是同一个套路在复利。