堆排序实战：从零手写高效原地排序，掌握数组中的二叉树逻辑

堆排序可能是所有主流排序算法里最被低估的一个。看起来它不像快速排序那样普及，但它是极少数能做到最坏情况 O(n log n)、额外空间 O(1) 的原地排序。很多朋友一听“堆”字就觉得难，实际动手写一遍就会发现，堆排序的骨架不过十几行代码。

这篇博文的定位很明确：带你从零手写一个能跑通的堆排序简单实现。不管是准备算法面试、复习基础数据结构，还是想彻底搞清楚优先队列背后的运作逻辑，这篇文章都适合你。我尽量用大白话把每一步的原理说透，并把所有容易翻车的边界、索引公式、坑点单独拉出来讲。你会发现堆排序不是背代码，而是看穿三件事：数组就是堆、下沉是唯一的操作、排序就是反复摘顶。

1. 堆排序入门到底难在哪：先从堆这个数据结构说起

1.1 数组与完全二叉树的映射关系

堆排序有个很反直觉的点：它不需要真的建一棵树，二叉堆是直接活在数组上的。你不需要用指针去分配节点，只需要把数组下标当成“树节点编号”，然后按规则想象一棵完全二叉树。

举个例子，数组 [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] 在逻辑上就是一棵高度为4的完全二叉树。下标0是根节点，下标1和下标2是它的左孩子和右孩子，下标3和下标4是下标1的两个孩子，以此类推。这棵树并没有真的在内存里存在，但所有堆操作都可以通过下标计算来模拟父子关系。

需要记住三个映射公式：

• 下标 i 的节点，父节点下标是 (i - 1) // 2
• 下标 i 的节点，左孩子下标是 2 * i + 1
• 下标 i 的节点，右孩子下标是 2 * i + 2

为什么左孩子是 2i+1 而不是 2i？因为数组从0开始编号，根节点是0，它的左孩子是1，右孩子是2；接着左孩子的左孩子是3，右孩子是4……按照层序遍历顺序为每个节点编号，就会发现这个偏移量是固定的。我以前也经常记混，后来直接在纸上画一棵4层的小树，把下标标上去，扫一眼就记住了。抽象公式如果不直观，画图永远是最好的补救办法。

1.2 最大堆和最小堆：到底谁是谁

堆的核心性质是一条约束：父节点的键值必须始终大于等于或者小于等于孩子节点的键值，两者取其一，并且整棵树都适用。

如果满足“父节点 >= 孩子节点”，就叫最大堆，也叫大顶堆，堆顶元素必然是全局最大值。如果满足“父节点 <= 孩子节点”，就叫最小堆，也叫小顶堆，堆顶元素必然是全局最小值。

初学者最容易把堆和二叉搜索树搞混。二叉搜索树的约束很严格，左子树的所有节点都小于根，右子树的所有节点都大于根；而堆的约束很宽松，只要求父子之间满足大小关系，兄弟之间谁大谁小完全不管，左右子树之间也没有大小次序要求。正是这种宽松约束，才让堆的建堆成本能降到 O(n)，因为不需要在全局维持一个严格的次序，只要局部家庭关系成立就行。

用生活化的类比来说，二叉搜索树像公司里的严格层级，上级必须压过左侧所有下级、低于右侧所有下级；堆更像球队排名，只要求队长比所有队员强，队员之间谁强谁弱，内部自行消化。升序排序时我们一般用最大堆，因为每一轮都能从堆顶拿到当前最大值，放到数组尾部，最后自然形成升序。

1.3 把堆排序理解成“选择排序的升级版”

先回想一下选择排序：第一轮从头到尾扫一遍，找出最小值放到第0位；第二轮继续扫描剩余 n-1 个，找最小值放在第1位。时间复杂度是典型的 O(n^2)，因为每找一次最小值都要线性遍历。

堆排序走的其实是同一条路：每一轮也是“找出当前剩下元素里的最大值”，放到数组末尾。区别只在于找极值的手段。选择排序用线性扫描，每轮 O(n)；堆排序用一个堆来维护候选，找一次堆顶只要 O(1)，把新元素挪上来之后恢复堆性质只需要 O(log n)。总成本从 O(n^2) 降到了 O(n log n)，本质上是换了个更聪明的数据结构来加速“找极值”这个动作。

想通这一点之后，堆排序在你眼里就不再是神秘算法了。它等于“优先队列 + 选择排序”。优先队列负责快速取出最大值并保持结构，选择排序的框架负责把取出来的值依次放到正确位置。建堆阶段就是先把数组组织成一个优先队列，排序阶段就是反复取队首、再修复队列。面试时如果被问到“堆排序的思路”，我建议也从这个角度切入，比起直接讲下沉代码，这种说法能让面试官一眼看出你真的理解了堆和选择排序的关系。

2. 堆排序的三大核心步骤：下沉、建堆、交换摘顶

2.1 下沉操作：堆排序中最重要的“最小动作”

堆排序的全部代码，本质上只有一个原子操作，叫下沉，也叫 sift down 或 heapify。理解了下沉，堆排序就学会了一大半。

什么情况下需要下沉？假设当前你站在下标 i 的节点上，左右子树各自都已经满足最大堆性质，但 i 节点自己可能比它的某一个孩子小。此时整棵子树不满足堆性质，你需要把 i 和较大的那个孩子交换，让大的上位。交换之后，i 移动到孩子的位置上，可能还是比新位置的孩子小，那就继续交换，直到它找到一个“两个儿子都比自己小”的位置为止。

下沉函数需要三个参数：数组本身、堆的有效长度 n、当前节点下标 i。这里“有效长度”容易被忽略，它表示“当前这个堆到底占数组的哪一段”。在排序阶段，堆的尾部会被不断切掉，如果你每次都用整个数组长度去下沉，逻辑就崩了。后面第3章代码里会反复验证这一点。

为什么整理堆用的是下沉而不是上浮？因为建堆和排序阶段的修复方向都是从根到叶。建堆时我们从最后往前处理，保证处理到下标 i 时它的左右子树都已经是合法堆，此时只需要把 i 往下送；排序阶段则是因为只有堆顶被换了新元素，也只需要从根往下推。上浮那一套是给堆插入场景准备的，在堆排序里基本用不上。

2.2 自底向上建堆：从最后一个非叶子节点动手

建堆的流程一句话就能讲完：从最后一个非叶子节点开始，逐个往前做下沉，一直做到下标0。但这句话里的“最后一个非叶子节点”怎么算，是个高频考点。

数组长度是 n，最后一个元素的下标是 n-1，它的父节点下标是 (n-1-1)//2，也就是 n//2 - 1。这个下标往后的节点全是叶子节点，比如 n=10 时，非叶子节点是 0 到 4，叶子是 5 到 9。叶子节点没有孩子，根本不需要下沉，所以建堆的起点就是 n//2 - 1。

为什么要从下往上建堆？因为下沉操作有一个前提：当前节点的左右子树必须已经是合法堆。如果你从根节点开始往下调，根的孩子子树还没整理好，下沉动作的前提根本不成立；但如果你从最底层开始，先保证每一个叶子以下的“小堆”都是合法的，再慢慢往上层处理，处理到任意节点时，它的左右子树都已经整理妥当，一次下沉就能让整棵子树变成一个合法堆。这个过程本质上就是后序遍历：先处理子树，再处理父节点。

2.3 排序阶段：每次把堆顶放到数组最后

建堆完成后，最大堆的堆顶就是数组里的最大值。排序阶段的循环动作看似只有三步，却是堆排序最精妙的组成部分。

第一步，把堆顶元素和当前堆的最后一个元素交换。这一步把最大值搬到了数组尾部，它从此离开堆的管辖范围，进入有序区。第二步，让堆的有效长度减1。注意这里的“有效长度”已经不是原始数组长度了，而是从0到当前末尾的这段区间。数组尾部的几个元素已经排好序，不能再参与堆的比较。第三步，对新的堆顶做一次下沉。交换上来的那个小元素往往不符合堆顶要求，把它往下沉，直到重新恢复最大堆性质。此时堆顶又变成剩下元素里的最大值。

重复 n-1 轮之后，所有元素都从堆的顶部被“摘”走、塞到数组末尾，数组自然变成一个升序序列。我常跟人说，排序阶段每一次的“交换 + 下沉”，就是一次“从优先队列取出最大值并维护队列”的操作，循环 n-1 次，整个数组就排好了。

注意：每一轮下沉函数里传入的 n，永远是“当前堆的有效长度”，不是整个数组的最初长度。这个变量没理解透，堆排序代码大概率会在小数据上偶然正确、大数据上翻车。

3. 简单实现：两种主流语言的完整代码

3.1 Python版本：一行一行读得懂的堆排序

我自己的经验是，Python版本最适合做入门用途，原因有两个：代码短，可读性强；不需要处理 C++ 那种容易把人带偏的 size_t 陷阱。先看完整代码：

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 heapsort(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[0], arr[i] = arr[i], arr[0] heapify(arr, i, 0)

核心逻辑不到20行。heapify 里先假设当前节点 i 是最大值，然后分别检查左孩子和右孩子，如果有比 largest 还大的就更新 largest。只要 largest 不是 i，说明孩子里存在更大值，交换两者，并继续对新位置做递归下沉。

这里有三个容易看走眼的点。第一，arr[left] > arr[largest] 用的是严格大于，意味着值相等时不交换，这不会破坏堆性质，还能减少不必要的交换。第二，条件里必须有 left < n 和 right < n，因为最后一个节点的右孩子可能不存在，不判断就会数组越界。第三，排序阶段的 heapify(arr, i, 0) 中那个 i 是有效长度，不是初始的 n，这正是前面反复强调的重点。

3.2 C++版本：面试手写最常见的形态

面试手写堆排序时，C++ 是最常见的形态，因为很多公司面试官就是 C++ 背景。这里我给出一个稳妥版本，同时把递归改成了迭代，降低栈依赖：

#include <vector> #include <algorithm> using namespace std; void sift_down(vector<int>& arr, int n, int i) { while (true) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest == i) break; swap(arr[i], arr[largest]); i = largest; } } void heap_sort(vector<int>& arr) { int n = (int)arr.size(); if (n < 2) return; for (int i = n / 2 - 1; i >= 0; --i) { sift_down(arr, n, i); } for (int i = n - 1; i > 0; --i) { swap(arr[0], arr[i]); sift_down(arr, i, 0); } }

迭代版下沉的核心是那个 while(true) 循环：每一轮找出当前节点、左孩子、右孩子中最大的，如果最大值就是自己，说明局部已经满足堆性质，立刻 break；否则交换并移动 i 继续下一轮。这样写比递归版多几行，但对边界条件更直观一些。

在 C++ 里，我最想提醒三件事。第一，n 一定要显式转成 int，不要用 size_t，因为循环里 i 会递减到负数，size_t 会下溢成一个巨大的数，循环彻底失控。第二，arr.size() 为 0 或 1 时直接返回，避免 n/2-1 算出负数后循环条件混乱。第三，排序阶段的 sift_down(arr, i, 0) 中的 i，是和 Python 版本一样的“当前堆有效长度”，不是 arr 的原始大小。

3.3 验证排序结果的通用测试方法

写完算法先别急着撒手，我见过太多人用一两个手写例子验证完就认为程序对了，结果随机数据上跑一下立刻露馅。可靠的验证方式其实很简单：写一个随机测试脚本，循环很多次，每次生成随机数组，用标准库排序结果做基准，再和你的堆排序结果做断言。Python 可以这样写：

import random def check_heap_sort(): for _ in range(10000): data = [random.randint(-1000, 1000) for _ in range(random.randint(0, 100))] expect = sorted(data) heapsort(data) assert data == expect, data print("all passed") check_heap_sort()

先把长度为0的空数组、长度为1的数组、只有两个元素的数组跑一遍，再跑随机数据，这是排序类代码最稳妥的测试顺序。边界数组能帮你抓住绝大多数由于 n//2-1 或者循环起始位置算错导致的崩溃。测试全部通过之后，你再去研究性能优化、堆结构可视化那些花活，基础就不会坍了。

4. 极易翻车的细节：索引、边界、稳定性

4.1 下标从0还是从1开始，公式完全不同

堆排序最大的坑不是算法思想，而是下标公式。市面上的经典教材习惯用 1-based 下标，树上父节点是 i/2，左孩子是 2i，右孩子是 2i+1。而现代编程语言里数组清一色 0-based，公式整体偏移一位：父节点是 (i-1)//2，左孩子是 2i+1，右孩子是 2i+2。我见过不少人照着经典教材的伪代码抄，然后把 0-based 数组当成 1-based 来用，最后要么越界，要么各种数据对不上。

我自己的笨办法是，每次写堆排序前先在纸上画一棵只有4个节点的小树，具体标出下标。根是0，左孩子是1，右孩子是2，1的左孩子是3。看一遍图，公式 left = 20+1、right = 20+2、parent = (3-1)//2 = 1 这些就全清楚了。真正上手面试时，如果一下子记不起来，也可以现场画这个小图推算，没有人会因为你画图而扣分，反而能体现你的思路严谨。

4.2 边界条件与递归终止的确认

下沉操作的终止条件不是“必须沉到叶子”，而是“当前节点已经是它这个子树里的最大值，不需要再交换”。回想一下，如果节点走到一半发现两个儿子都小于自己，这棵树局部已经合法了，就完成任务。很多人把这个终止条件写成递归的 base case，即 left >= n，这其实不对。因为如果当前节点虽然左孩子已经越界，但它的值仍然可能小于一个符合条件的右孩子，逻辑就乱了。正确做法是：每一轮先比较出三个候选里最大的下标，如果最大下标还是 i，才 break 或 return。

边界判断还有一个容易忽略的点：右孩子是否存在。完全二叉树里，最后一个非叶子节点可能只有一个左孩子，没有右孩子。如果你在代码里直接访问 arr[right]，在 n 的边界附近就可能越界。要么像示例代码那样写上 right < n 的判断，要么提前把 right 和 n 的关系判断清楚，二选一，但不能不写。

4.3 堆排序为什么不稳定

稳定性是指值相等的两个元素，排序前后相对顺序是否保持不变。堆排序是不稳定的，原因在于排序阶段的“摘顶”操作会把堆顶元素和当前堆的最后一个元素直接交换，这一脚可能让两个相等的元素位置反转。

举一个经典反例：初始数组 [2a, 2b, 1]，这里 2a 和 2b 代表两个值相同但身份不同的元素。建堆完成后，因为最大堆对相同值不区分先后，堆顶可能是 2a。排序阶段第一步把 2a 和末尾的 1 交换，得到 [1, 2b, 2a]；第二步堆顶 2b 与下标1交换后，最终数组是 [1, 2b, 2a]。原始顺序是 2a 在前、2b 在后，排序后变成 2b 在前、2a 在后，相对位置反转，铁证如山的不稳定。

面试官问“堆排序稳定吗”时，你可以先说结论“不稳定”，然后马上给出这个两三行的反例。能讲出具体反例和只背结论，给人的印象完全不一样。

5. 复杂度与横向对比：堆排序在算法江湖里的位置

5.1 建堆为什么是O(n)而不是O(n log n)

这是堆排序里最反直觉的复杂度结论。很多人一看“调整n个节点，每次下沉 log n”，就认定建堆是 O(n log n)。但你只要把节点分布算一下，就会发现账完全不对。

建堆需要下沉的节点一共有约 n/2 个非叶子节点。越靠近底层的节点数量越多，但它们需要下沉的次数却越少。最底层虽然有近 n/2 个节点，但它们全是叶子，下沉次数是0；倒数第二层有约 n/4 个节点，每个最多下沉1次；倒数第三层有约 n/8 个节点，每个最多下沉2次。把每一层的工作量加起来，整个建堆成本是 n/41 + n/82 + n/16*3 + ... ，这是一个收敛的等比级数，结果等于 O(n)。

换句话说，建堆阶段的大部分节点都太矮了，根本跳不了几层。那些需要下沉很多次的节点，也就是靠近根的少数节点，每次下沉的成本确实高，但数量太少，撑不起 O(n log n) 的总量。以后面试被追问“为什么建堆是O(n)”，能说出这层分布逻辑，会比只说结论加分很多。

5.2 排序阶段的复杂度分析

排序阶段没法享受建堆那种“底层免单”的福利。每一轮，堆顶元素被换走，新的堆顶往往是原来堆尾的小元素，它需要从高度为 log n 的根位置一路下沉，直到重新满足堆性质。这一轮的下沉成本稳定在 O(log n)，而一共要执行 n-1 轮，所以排序阶段是 O(n log n)。

把两个阶段加起来：O(n) + O(n log n) = O(n log n)。堆排序的空间复杂度则是 O(1)，因为只有交换时用了一个临时变量，所有操作都在原数组上进行，属于原地排序。这一点在内存紧张且对最坏时间有硬性要求的场景里，比归并排序更有优势。

5.3 堆排序、快排、归并：三者的对比与取舍

三个排序算法放在同一个桌上，经常让人纠结。我直接列一张表，把关键指标放一起：

这张表看下来，堆排序好像也不差：最坏情况下没快排那么糟，空间上没归并那么大开销。那为什么工程库的 sort 类算法往往选择快排或者快排的变种，而不是堆排？

原因有两个。第一，快排的常数因子小。所谓“复杂度相同”，指的是增长率同阶，但堆排序里每次比较都是在不相邻的下标之间跳跃，缓存局部性差；快排是顺序扫描式访问，CPU缓存友好。在百万级以上的真数据上，快排通常明显更快。第二，堆排序的交换次数和比较次数在常数部分也比快排多，这是算法结构决定的。

但堆排序的价值从不在“通用排序”上，而在于它的核心数据结构本身。优先队列、TopK、定时器、任务调度，这些场景都比“排一次序”更常见。这也是我想用第6章展开说的点。

6. 实战场景与常见问题排查

6.1 用堆解决TopK问题的极简写法

堆排序的一个经典延伸是大批量数据里的 TopK 问题。比如有1亿条日志记录，内存放不下所有数据，但你只想要最大的100条。这时候对整个数据集排序再取前K个太奢侈，用一个大小为K的小根堆就能在遍历一遍的过程中搞定。

先理解思路：维护一个K个元素的小根堆，堆顶是整个堆里最小的元素。扫描数据时，每遇到一个比堆顶大的元素，就把堆顶替换成它，然后下沉恢复小根堆性质。最终堆里的K个元素就是全局最大的K个。Python里可以直接用内置的 heapq：

import heapq def top_k_largest(arr, k): if k <= 0: return [] heap = arr[:k] heapq.heapify(heap) for x in arr[k:]: if x > heap[0]: heapq.heapreplace(heap, x) return sorted(heap, reverse=True)

heapreplace 内部其实就是“先弹出堆顶、再插入新值、最后从根下沉”的组合动作，展开来就是堆排序三件套里“摘顶+下沉”的事。所以千万不要以为 TopK 和堆排序是两码事，它们的底层操作是同一套。整体复杂度是 O(n log k)，当 k 远小于 n 时非常划算。如果面试要求你手写这个过程，就把 heapreplace 拆成“移除堆顶 → 添加新值 → 下沉”三步来实现，代码长一点，但逻辑上是同一件事。

6.2 调试实录：我写堆排序时踩过的三个坑

这些年我手写过很多次堆排序，该踩的坑基本都踩了一遍。第一个坑是建堆起点写错。我有段时间老是把range(n // 2 - 1, -1, -1)写成range(n // 2, -1, -1)，结果多处理了一个叶子节点。偶尔数据量小的时候没事，数据量大一点或者数组结构特殊就开始随机出问题。后来我养成了习惯：写排序算法先用长度为4或5的小数组手工推演一遍，再跑随机测试。小数组里能一眼看出每一轮交换是否合理。

第二个坑是排序阶段没把有效长度传对。我曾经在循环里调用heapify(arr, n, 0)，用的是最初数组长度，导致已经归位到数组尾部的元素再次被“拖回”堆里参与比较和交换。表面看数组依然有序，实际上相等元素的顺序已经被搅乱。后来我每次写排序阶段循环，都会在代码注释里写上“这里传入 i 表示当前堆的有效长度，不是原始 n”，防止自己再犯。

第三个坑是 C++ 版本里的 size_t。当年犯过的错误：for (int i = n / 2 - 1; i >= 0; --i)用 int 时没问题，但换到 size_t 定义的 n 后，i 减到 0 再继续--会直接下溢成一个巨大正数，循环飞掉。现在我在所有排序代码里禁用 size_t 做循环变量，宁可用 int，至少不会因为负数下溢把自己坑进死循环。

6.3 面试与工程中堆排序的真正定位

堆排序在算法面试里很少作为独立大题出现，更多时候它是某个复杂问题里的一个环节。比如“数组第 K 大元素”“合并 K 个有序链表”“数据流中实时取中位数”，这些题目的标准解法都依赖堆。你需要快速判断出：这里应该用小顶堆还是大顶堆，堆的容量是 K 还是动态变化，是建一次堆还是边插入边调整。这些判断能力，本质上就是你对建堆、取顶、下沉这三件套的熟练度。

在工程源码里，堆也经常以“救火队员”的身份出现。C++ 的 std::sort 是内省排序，平时用快排思路，但当递归划分深度过深、有退化到 O(n^2) 的风险时，它会切换成堆排序来兜底。这说明堆排序虽然当全职选手差点意思，但保证最坏情况复杂度这件事，它特别可靠。

我自己在实际项目里，几乎没直接调用过一个“堆排序函数”，但写定时器、优先队列、调度器时，天天都在和堆的建堆、下沉、取顶逻辑打交道。所以学堆排序，我更建议你把它当成“优先队列的三板斧”来学，而不是仅仅背一个排序函数。一旦这个思维转了，后面遇到需要动态维护极值的问题，你会比别人快一拍想到堆。

这些年我每次复习堆排序，都会重新手写一遍。目的不是为了背代码，而是把索引公式和下标的逻辑重新过一遍脑子。写多了你会发现，最容易出错的根本不是算法思想，而是那一个又一个 n//2-1、2*i+1、n 和 i 的边界切分。最后分享一个小习惯：把代码里“当前堆有效长度”这个变量单独起名叫 heap_size，和数组长度在命名上区分开，这一招至少能帮你避开一半我踩过的坑。堆排序不难，难的是你愿不愿意静下心来推演一次完整过程；推过之后，它就会变成你脑子里随时能调出来的工具。