堆排序算法详解：从完全二叉树到下沉操作与TopK实战

排序算法里，堆排序一直处在一种“人人都知道、人人讲不清”的位置。很多人能背出它最坏情况 O(n log n)、不稳定、原地排序这几个标签，可真要手写一遍，十个里有八个会在“结束下标到底该传多少”“右孩子到底存不存在”这种地方卡壳。堆排序本质上不是一种花哨的排序技巧，它是堆这个数据结构最经典的一次落地：把完全二叉树装进数组，用父子下标的数学关系组织数据，再通过堆顶不断输出当前最大值，最终完成升序排列。这篇文章我想从“数组里的那棵看不见的树”讲起，把堆排序的每个动作拆到能徒手推演的程度。适合三类人：想系统搞懂堆数据结构的初学者、面试前需要手写排序的求职者、以及在实际项目中想用堆解决 TopK、优先队列等问题的工程师。

1. 排序之前，先看懂“堆”这个数据结构

1.1 最大堆、最小堆与完全二叉树的约束

堆排序的主角是“堆”。堆首先是一棵完全二叉树，然后在这棵树上追加一条排序规则：每一个父节点的值都不小于自己的两个孩子，这叫最大堆；如果每一个父节点都不大于两个孩子，就叫最小堆。完全二叉树这个约束非常关键，它要求除了最后一层，前面每一层都必须填满，最后一层的节点也要从左到右连续排列，中间不能出现空位。换句话说，这棵树不允许“右子树还存在但左子树已经缺失”的畸形结构，它天然适合压缩进数组。

想理解为什么堆排序性能能稳定在 O(n log n)，就要先理解这棵树的“矮胖”特性。一棵节点数为 n 的完全二叉树，高度严格等于 floor(log2 n)，每一层都相对密集，这让任何从根到叶子的路径长度都被限制在 O(log n)。堆排序的每一次“堆顶拿走、末尾替上、向下调整”，本质上都是在这样一条不超过 log n 级别的路径上做文章。这也是堆能成为高效优先队列的根本原因。

1.2 用数组表示堆：父子下标的关系换算

堆排序的关键动作不是建指针，而是用下标换算关系。假设数组从下标 0 开始存，对于任意下标 i，它的左孩子下标是 2 * i + 1，右孩子下标是 2 * i + 2，父节点下标是 (i - 1) // 2。由于完全二叉树的连续占用特性，数组中的相邻区间天然对应着树的层级，不需要额外分配结构体，不需要指针跳转，直接用下标加减就能完成父子游走。

这里必须强调一个很容易混淆的点：很多教材习惯把数组当成从 1 开始编号，那公式就变成左孩子 2 * i、右孩子 2 * i + 1、父节点 i // 2。这两种约定都能工作，但绝不能混用。我用下标 0 做基准演示时，看到过太多人写着写着左手用了 0-based 公式、右手按 1-based 逻辑计算边界，最终导致节点访问错乱。写代码之前先想清楚一件事：数组下标 0 那个位置到底存不存有效数据？存，就用 0-based 的一套公式从头贯穿到尾；不存，才允许用 1-based 的教科书写法。强烈建议统一采用 0-based，因为绝大多数编程语言数组天然从 0 开始，这样写循环边界时心智负担最小。

1.3 为什么堆排序默认用最大堆而不是最小堆

堆排序的目标如果是升序输出，那么请建立最大堆而不是最小堆。理由很直接：最大堆保证堆顶是当前堆内全局最大值，把它交换到数组末尾之后，最大值就位；下一次再在缩小的堆范围内取堆顶，得到次大值，继续塞到末尾倒数第二个位置。这样一轮一轮取最大，最终数组从后往前依次被填上降序的“最大、次大、第三大”，整体呈现升序。如果建立最小堆，堆顶是全局最小值，取出来放末尾会得到降序结果。虽然不能说最小堆不能排序，但最大堆配合“取最大放尾部”的做法是堆排序最自然的形态。

这一点在实现优先队列时同样适用：需要频繁取最小值的场景用最小堆（小顶堆），需要频繁取最大值的场景用最大堆（大顶堆）。堆排序只是“顺带利用”了最大堆的取顶能力，真正被广泛使用的是这种“堆顶总是极值”的结构特性，而不只是最终的排好序数组。

2. 下沉、上浮和建堆的底层逻辑

2.1 下沉操作：堆排序的心脏

堆排序里最重要的单一操作是“下沉”（sift down）。在最大堆中，下沉的场景是：某个位置的元素比它的孩子小，破坏了堆顶最大规则，需要通过不断向下交换，让这个“不够格”的节点回到合适的位置。具体步骤是：先看当前节点有没有左孩子，有左孩子再看右孩子是否存在，从左右孩子中选出值更大的那一个，然后把这个更大值与当前节点比较；如果当前节点更小，就交换两者，接着以交换后的新位置继续重复这个过程，直到当前节点不再小于任意孩子，或者已经到达叶子层。

有一个细节经常被初学者忽略：为什么必须从左右孩子里选“更大的”那个交换，而不是随便挑一个比父节点小的孩子？因为一次交换之后，被换上去的孩子会顶替父节点的位置，它必须比它的兄弟节点更大，否则它作为新子树根会再次小于兄弟，堆顶规则立刻又被破坏，后续还得额外处理。先选出最大孩子再比较，一次交换就能把“小的往下放”这件事做到位，这才是下沉操作里最关键的一步。用生活类比就是：一个队伍里要让能力最差的人退位，接手的人必须是剩下的最强竞争者，否则新上位的人立刻又会带崩整个小组。

下沉操作的输入参数有讲究：不仅要知道待下沉的节点下标 start，还要知道当前堆的有效边界 end。因为排序过程中数组末尾那段已经放着排好的元素，不属于堆了，下沉绝对不能越界跑到已排好序的“禁入区”里去。

2.2 建堆为什么要自底向上、从最后一个非叶节点开始

构建最大堆的常规做法不是从根节点开始往下“压”，而是从最后一个非叶子节点开始，逐步往前执行下沉。最后一个非叶子节点的下标很好算：总长度 n 时，下标为 n // 2 - 1（0-based）。为什么从它开始？因为叶子节点本身就是一个单元素堆，天然合法，不需要调整。只有从叶子层的上一层开始，才能保证每个节点在往下沉时，它的左右子树已经是合法的堆。

如果反过来从根节点开始建堆，会出现一个很尴尬的场面：你无法保证当前节点的子树已经是堆，下沉一次只能解决局部大小关系，无法把子树内部的错误顺带修正，整体调整次数会显著增加。自底向上的顺序，本质上是在每一层搭建“局部有序的地基”，上层依赖下层的结果。这个顺序是堆排序乃至整个堆结构建堆操作的性能关键。

2.3 上浮操作到底在堆排序里起不起作用

很多讲解堆的文章会同时介绍“上浮”（sift up），它的典型场景是往已存在的堆里插入一个新元素：把新元素放到数组末尾，然后不断和父节点比较，如果比父节点更大就交换，一路往上冒。这是优先队列在插入时的主要操作。但堆排序的完整流程里其实没有插入动作，它的构建阶段全部用下沉完成，排序阶段也全部用下沉完成，所以上浮在“纯堆排序算法”中并不会出现。

那为什么还要理解上浮？因为面试和实际工程里经常会遇到半路在排好堆的情况下追加元素的需求，特别是在线维护 TopK 或优先队列时。只要理解了“下沉是顺着孩子路径处理破坏堆顶的问题，上浮是顺着父路径处理新元素破坏父节点规则的问题”，你在碰到动态插入时就不会发怵。堆排序本身不需要上浮，不代表这种原语没有价值，只是别在日常写排序时误混进堆排序流程里，否则代码会变得又长又难查。

3. 堆排序完整流程与一份可直接运行的参考实现

3.1 三步走：建堆、交换、缩小堆范围重新堆化

堆排序的整体流程可以压缩成三个阶段。第一阶段，把所有乱序数据通过自底向下沉打造成一个合法最大堆，这一步完成后，堆顶必然是全数组最大值。第二阶段，交换堆顶和当前堆末尾元素，最大值就此进入数组的最终位置。第三阶段，把堆的边界向左收缩一位，处理刚才被换到堆顶的那个“末尾元素”，对它执行一次下沉，让剩余部分再次成为最大堆。然后重复第二和第三阶段，直到堆里只剩一个元素，排序结束。

这里最反直觉的一点是：排序过程中被换到堆顶的不是一个“新最大值”，而是堆尾的某个普通元素，它大概率不满足堆顶要求，所以每次交换之后都需要重新下沉。这其实是一种很划算的策略，因为下沉一个元素的最坏代价是 O(log n)，排序阶段总共执行 n-1 次交换和下沉，总复杂度就是 O(n log n)，这个上界非常稳定，不受输入数据原本是否有序影响。

3.2 一份 Python 实现的关键代码剖析

下面这份实现基于 0-based 下标、闭区间 end 写法，我特意把下沉函数写得足够独立，方便读者把它抽出来单独测试。

def sift_down(arr, start, end): """最大堆下沉调整。 arr: 目标数组 start: 待下沉的父节点下标 end: 当前堆的有效右边界下标，闭区间 """ father = start while 2 * father + 1 <= end: child = 2 * father + 1 # 左孩子 swap_pos = child # 如果右孩子存在且更大，则选择右孩子 if child + 1 <= end and arr[child + 1] > arr[child]: swap_pos = child + 1 # 父节点已经比最大的孩子大，说明堆合法，退出 if arr[father] >= arr[swap_pos]: break arr[father], arr[swap_pos] = arr[swap_pos], arr[father] father = swap_pos def build_heap(arr): n = len(arr) for i in range(n // 2 - 1, -1, -1): sift_down(arr, i, n - 1) def heap_sort(arr): build_heap(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-1

代码里有几个地方需要重点强调。首先，sift_down 接受的是闭区间 end，也就是“当前堆的最后一个有效下标”，所以建堆时传 n-1，排序中交换后传 end-1，这是新手最容易写错的地方。其次，while 循环的判断条件是2 * father + 1 <= end，意味着必须保证左孩子存在；右孩子在child + 1 <= end时才考虑比较，这是防止数组越界的核心防线。最后，当arr[father] >= arr[swap_pos]时直接 break，不要继续换，即使相等也无需交换，少做一次没有任何意义的赋值操作，也能省下一点点常数时间。这段代码在 LeetCode 这类在线判题环境直接运行是没问题的，你完全可以把它当成背诵模板，但更重要的是要能清楚讲出每一步为什么这么做。

3.3 手推一个小数组，验证全过程

空谈概念太抽象，我用一个小数组[4, 10, 3, 5, 1]完整推演一遍。先建堆，数组长度为 5，最后一个非叶子节点下标为5 // 2 - 1 = 1，即下标 1 对应的元素 10。它的左孩子是下标 3 的 5，右孩子是下标 4 的 1，最大孩子 5 小于 10，所以位置 1 不用动。接着处理下标 0 的元素 4，左孩子是下标 1 的 10，右孩子是下标 2 的 3，选中更大的 10，交换后数组变成[10, 4, 3, 5, 1]。元素 4 现在位于下标 1，继续看它的孩子，左孩子是下标 3 的 5，右孩子是下标 4 的 1，最大孩子 5 大于 4，交换后数组变为[10, 5, 3, 4, 1]，建堆完成。

进入排序阶段，第一轮交换堆顶 10 和堆尾 1，数组变成[1, 5, 3, 4, 10]，堆的有效范围变成下标 0 到 3，10 已经固定。对下标 0 的 1 执行下沉，左右孩子分别是 5 和 3，选择 5 交换，数组变为[5, 1, 3, 4, 10]；继续下沉，1 的左孩子是下标 3 的 4，右孩子越界，4 比 1 大，交换后数组变为[5, 4, 3, 1, 10]。第二轮交换 5 和堆尾 1，数组变成[1, 4, 3, 5, 10]，堆范围缩到下标 0 到 2，下沉后 4 换到堆顶，数组变为[4, 1, 3, 5, 10]。第三轮交换 4 和 3，数组变成[3, 1, 4, 5, 10]，堆范围 0 到 1，下沉时 3 大于 1，不用调整。最后一轮交换 3 和 1，整个数组变为[1, 3, 4, 5, 10]。走完这一遍，你会发现每一轮交换之前堆顶都是当前堆最大值，这个性质始终没有被破坏。

4. 复杂度、稳定性与实战场景的选择依据

4.1 建堆为什么是 O(n)，排序为什么是 O(n log n)

堆排序整体复杂度是 O(n log n)，但其中建堆那一步其实是 O(n)，不是 O(n log n)。这个结论第一次接触时很容易让人觉得不对，毕竟每个节点下沉一次不是 O(log n) 吗？关键在于：不是每个节点下沉都会有 log n 的高度。完全二叉树里，越靠近底层的节点数量越多，但它们各自的高度很小；越靠近根部的节点高度大，但数量很少。把对每一层的下沉代价求和，会得到类似“1 * (n/2) + 2 * (n/4) + 3 * (n/8) + ...”这样的级数，这个级数收敛于 O(n)。所以建堆阶段的代价是线性级别，堆排序的时间瓶颈在排序阶段：n-1 次取堆顶，每次下沉最坏 O(log n)，合计 O(n log n)。

值得警惕的是，堆排序的“最好情况”和“最坏情况”都是 O(n log n)。不像快速排序那样对有序数组特别敏感，也不像插入排序那样在近乎有序的数据上能退化到 O(n)。这种“无论你喂什么数据，时间波动都不大”的特点，让堆排序在实时性要求高的系统中很有吸引力，它不会突然因为数据形态变差而出现性能尖刺。

4.2 空间复杂度与原地排序的意义

堆排序的空间复杂度是 O(1)，因为它只需要在原始数组内部做交换，不需要像归并排序那样额外开辟一个等长数组，也不需要像快速排序那样在递归时承担平均 O(log n) 的栈空间。这里的“O(1)”是指额外辅助空间，递归版本会因为递归栈引入 O(log n) 开销，不过我给的迭代版 sift_down 连递归栈都不需要，真正的额外消耗只有几个临时变量。

这个特性在内存受限的嵌入式环境里很值钱。我曾经在某个内存以 KB 计的边缘设备上做过实时统计排序，数据规模不算大但内存极其紧张，归并排序根本无法展开，快排的递归栈又让人心里没底，最后就是用堆排序收尾。它不需要额外数组，只需要在原有缓冲区里腾挪，输出结果也完全满足需求。类似的场景还有数据库外部排序前的内存预排序、实时日志系统的 TopN 统计，堆排序在这一类场景中远比它作为“通用排序”更有存在感。

4.3 堆排序不稳定的原因与影响

堆排序是非稳定排序。稳定性的意思是：两个值相等的元素，在排序结束后，它们在原数组中的相对先后顺序能不能保持。堆排序做不到这一点，因为它的核心交换动作“堆顶与堆尾交换”会把相隔很远的两个元素瞬间换位。考虑数组[5a, 1, 5b, 2]，建堆之后两个 5 的相对位置很可能已经变化，而后续交换堆顶会让其中一个 5 直接跳到数组末尾，完全打乱同值元素的原有次序。过程中没有任何一个机制去保证同值元素的相对顺序，这就是它不稳定的本质原因。

业务系统中如果后续需要按多关键字排序，或者前面排好序的结果要依赖原顺序做二次合并，就一定要避开堆排序。比如一个在线表格要按“时间升序，时间相同按行号升序”展示，堆排序直接不可用，因为行号顺序会被打乱。这时候稳定排序（归并、插入、冒泡）才是正确的选择。很多新手只记“堆排序不稳定”这个结论，却不理解背后的交换机制，遇到真实业务时仍然会误用。

4.4 什么时候该用堆排序，什么时候别用

综合来看，堆排序不是一个“万金油”排序，但它在四类场景中特别能打。第一类是大数据量下只取前 K 个最大或最小元素，这种情况下完全没必要全量排序，维护一个大小为 K 的堆，每次有新元素就与堆顶比较，远比全排序高效。第二类是嵌入式或内存受限环境，原地排序是硬需求。第三类是实时性敏感系统，需要严格可预测的时间上界，堆排序不会因为数据分布出现剧烈波动。第四类是动态数据流中的优先队列，堆本身就是优先队列的最自然实现，堆排序只是它的一个副产品。

反过来，如果只是普通业务系统对中小规模数据做全量排序，堆排序通常不是最佳选择。快排的常数项更小，平均性能更好；归并排序稳定且适合链表和外部排序；插入排序在数据近乎有序时极其炸裂。堆排序最尴尬的地方是：它交换次数相对较多，而且对数组访问是跳跃式的，缓存局部性远不如快排，在处理几百万元素的通用排序时实际跑起来往往比快排慢。别被“都是 O(n log n)”迷惑，复杂度的常数项在真实机器上差距明显。

5. 常见问题与调试经验速查

5.1 数组越界与边界条件：两个孩子都要检查

堆排序最常见的崩溃就是数组越界，根源几乎都出在孩子下标计算。下沉循环里，每次都要先检查左孩子下标是否越界，也就是2 * father + 1 <= end，这代表当前节点还有至少一个孩子。在这之后访问右孩子，必须先确认child + 1 <= end成立，否则右孩子下标已经跑到堆的有效范围外。我见过不少人只检查左孩子，然后直接比较左右孩子哪个更大，结果右孩子是越界值，程序当场报错。这类问题用调试器很难一次看清，因为越界位置随数组变化，最好的方式是在代码里把所有边界判断写明确，每一处涉及右孩子访问的地方都单独做一次判断。

还要注意一个隐蔽的边界问题：当堆的有效范围已经缩小到只剩一个节点时，下沉函数根本没有必要执行，heap_sort 的主循环也会在 end 递减到 1 时结束，不会触发这个分支。但如果你把主循环条件改成range(len(arr)-1, -1, -1)，就会多跑一次多余操作，虽然不一定报错，但容易让后续逻辑变得糊涂。

5.2 下标公式混用的典型错误

下标公式混用是我见过频率最高的一种错误，而且它的表现形式非常狡猾。比如有人建堆时用range(len(arr)//2, -1, -1)，这其实是把 1-based 的 n/2 思路混进了 0-based 数组。表面上代码不报错，数组也能跑出结果，但建出来的树根本不是合法堆，某些父子关系是错位的，最后排序结果会出现“大体有序但个别偏大元素跑到前半段”的诡异现象。

排查这种问题最简单粗暴的方式是：写一个独立函数验证父子规则。选出任意父节点下标 i，断言它的值不低于左孩子、右孩子，遍历整棵堆。只要合法堆的性质被破坏，程序立刻输出错误的父与子下标，你就能快速定位是哪一层、哪一个节点出了问题。不要靠肉眼盯代码，堆的层数一多，人眼很难看出下标错乱。

5.3 堆排序调试心得：分段观察法与边界用例

我调试堆排序时最常用的方法是“分段观察”。不管数组是什么形态，每次交换堆顶和末尾之后，整个数组的逻辑结构一定可以分成两段：右侧是已经排入最终位置的升序尾巴，左侧是仍然保持堆结构的“活跃区”。调试时打印每一轮结束后的数组，先确认右侧尾巴的元素是否严格升序，再验证左侧堆顶是否是左侧最大值。只要这两点同时成立，算法运行下去一定正确。把所有中间状态打出来之后，错误往往一眼就能看出：要么是某次堆顶没有统计到最大值，要么是交换后的堆范围算错了。

边界用例也有固定套路。最小数组[ ]和[1]需要保证代码不崩溃；两元素数组[3, 1]能验证建堆和最后一轮交换逻辑；全相等数组[7, 7, 7, 7]能验证 break 条件是否正确触发。这些边界用例写起来十分钟不到，却能拦截掉大量深层逻辑错误。

5.4 常见问题对照表

收尾：一点真实体会

我最早手写堆排序的时候，花了两天才彻底搞明白为什么排序阶段每次都要把堆的 end 减一，而且下沉函数传进去的结束下标必须跟着变。后来才发现，只要自己心里时刻记住“数组右侧是已排序区，左侧是堆区”这张图，所有边界问题都会瞬间清晰。堆排序这个算法，光背代码是没用的，它考察的其实是你对完全二叉树和数组映射关系的理解程度。另外再分享一个实用扩展：很多一线系统真正需要用到的根本不是全量堆排序，而是“固定大小的小顶堆 + 新元素与堆顶比较”这种 TopK 方案，它在海量数据流里能避免一次性加载全部数据，实用性比完整排序高出一大截。你要是把这里的下沉函数和堆结构理解透了，再去写 TopK、优先队列和索引堆都会顺手很多。