堆排序可能是所有主流排序算法里最被低估的一个。看起来它不像快速排序那样普及但它是极少数能做到最坏情况 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为什么左孩子是 2i1 而不是 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。这个下标往后的节点全是叶子节点比如 n10 时非叶子节点是 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(vectorint 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(vectorint 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右孩子是 2i1。而现代编程语言里数组清一色 0-based公式整体偏移一位父节点是 (i-1)//2左孩子是 2i1右孩子是 2i2。我见过不少人照着经典教材的伪代码抄然后把 0-based 数组当成 1-based 来用最后要么越界要么各种数据对不上。我自己的笨办法是每次写堆排序前先在纸上画一棵只有4个节点的小树具体标出下标。根是0左孩子是1右孩子是21的左孩子是3。看一遍图公式 left 201、right 202、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 堆排序、快排、归并三者的对比与取舍三个排序算法放在同一个桌上经常让人纠结。我直接列一张表把关键指标放一起算法平均复杂度最坏复杂度额外空间稳定性快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定这张表看下来堆排序好像也不差最坏情况下没快排那么糟空间上没归并那么大开销。那为什么工程库的 sort 类算法往往选择快排或者快排的变种而不是堆排原因有两个。第一快排的常数因子小。所谓“复杂度相同”指的是增长率同阶但堆排序里每次比较都是在不相邻的下标之间跳跃缓存局部性差快排是顺序扫描式访问CPU缓存友好。在百万级以上的真数据上快排通常明显更快。第二堆排序的交换次数和比较次数在常数部分也比快排多这是算法结构决定的。但堆排序的价值从不在“通用排序”上而在于它的核心数据结构本身。优先队列、TopK、定时器、任务调度这些场景都比“排一次序”更常见。这也是我想用第6章展开说的点。6. 实战场景与常见问题排查6.1 用堆解决TopK问题的极简写法堆排序的一个经典延伸是大批量数据里的 TopK 问题。比如有1亿条日志记录内存放不下所有数据但你只想要最大的100条。这时候对整个数据集排序再取前K个太奢侈用一个大小为K的小根堆就能在遍历一遍的过程中搞定。先理解思路维护一个K个元素的小根堆堆顶是整个堆里最小的元素。扫描数据时每遇到一个比堆顶大的元素就把堆顶替换成它然后下沉恢复小根堆性质。最终堆里的K个元素就是全局最大的K个。Python里可以直接用内置的 heapqimport 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, reverseTrue)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*i1、n 和 i 的边界切分。最后分享一个小习惯把代码里“当前堆有效长度”这个变量单独起名叫 heap_size和数组长度在命名上区分开这一招至少能帮你避开一半我踩过的坑。堆排序不难难的是你愿不愿意静下心来推演一次完整过程推过之后它就会变成你脑子里随时能调出来的工具。