1. 为什么排序算法这么多我偏偏觉得堆排序最值得手写一遍如果要把排序算法按“出镜率”排个队堆排序绝对不会是出场次数最多的那个但它绝对是最值得手推一遍的算法之一。原因很简单它把“树形结构”和“数组”这两件事焊在了一起用完全二叉树的方式管理一段连续内存再用交换代替插入以O(nlogn)的时间复杂度完成原地排序。整篇文章不会只给你贴一段代码而是把堆排序背后“为什么这样想”“为什么复杂度是这样”“手写时哪里容易崩”揉碎了讲清楚。适合正在准备算法面试、需要手写TopK方案、或者想彻底搞懂优先队列原理的开发者。排序算法家族相当庞大插入排序、选择排序、冒泡排序、归并排序、快速排序、计数排序、基数排序每一个都有自己的脾气。堆排序在里面位置很特殊因为它是少数几个“明明不怎么被当成默认排序用却又到处都能看到其影子”的算法。你打开标准库里的PriorityQueue底层就是堆做海量数据TopK堆是教科书级方案操作系统任务调度、Dijkstra最短路的优化同样离不开堆。所以理解堆排序不只是学会一个排序算法而是同时把二叉堆、完全二叉树、优先级队列、堆调整操作这一整套思想全部打通。我见过不少朋友学堆排序时直接背代码背得很快但过两周再手写又崩了。这是因为堆排序的难点不在思路上而在“数组下标映射”和“边界条件”这种细节上。只要你能用一句话说清楚“大顶堆里每个父节点都必须不小于子节点”然后亲手写过几遍下沉操作堆排序基本就是顺手的事。这篇文章我会从数据结构底层开始讲到复杂度推导再到边界坑点最后聊聊它在真实工程里的定位。不求你背会一份万能代码只求你看完之后能在白板上心情平静地把它逼写出来。2. 数组、完全二叉树和堆先把“为什么数组能当树用”讲透2.1 数组和完全二叉树的映射关系堆排序里的“堆”本质是一棵完全二叉树而完全二叉树最大的好处是可以用数组连续存储不浪费任何下标。打个比方你把一棵树从上到下、从左到右一层层展开每个节点对应数组里的一个位置父子关系不用存指针直接用下标算出来。这里必须统一一个基准数组下标通常从0开始所以对于任意节点下标i左孩子下标是 2 * i 1右孩子下标是 2 * i 2父节点下标是 (i - 1) / 2向下取整即可如果你习惯从1开始编号那公式会变成左孩子2i、右孩子2i1、父节点i/2。我不建议在实现里混用这两种规则绝大部分翻车现场都是因为一会儿用0基公式一会儿又下意识套1基公式。这么多年的经验告诉我直接用0基公式写代码时不容易错因为在大多数编程语言里数组天然是0基的。2.2 大顶堆和小顶堆分别解决什么问题二叉堆在具体业务里分为大顶堆和小顶堆。大顶堆的要求是每个父节点的值都不小于它的两个孩子节点所以堆顶一定是最大值。小顶堆反过来父节点不大于孩子节点堆顶一定是最小值。很多人会问堆排序用的是哪个如果是升序排序就建大顶堆如果是降序排序就建小顶堆。这样设计是有讲究的我们后面会看到堆排序的核心循环是“把堆顶元素扔到数组末尾”因此升序场景下用大顶堆每次把最大值放到当前未排序区间的最后正好形成递增序列。大顶堆和小顶堆在很多场景下没有绝对的好坏选择标准完全看你需要最快拿到最大值还是最小值。比如TopK问题里要求返回最大的K个数你有没有想过为什么标准做法是用一个大小为K的小顶堆因为当堆满K个元素后新元素只要跟堆顶比较当前堆顶是这K个候选里的最小值如果新元素比它还小那新元素肯定不属于最大K个如果比它大就替换堆顶并做下沉调整。这套逻辑用大顶堆反而麻烦用大顶堆存“最大的K个”你还得记录这K个里到底谁是最小的每来一个新元素都要遍历一次性能直接退化。2.3 上浮和下沉维护堆性质的两板斧堆结构最重要的操作不是排序本身而是维护“堆性质”的两种调整动作上浮sift up和下沉sift down。上浮用于往堆里插入新元素。插入的时候我们先把新元素放到数组尾部然后不断跟父节点比较如果比父节点更适合做堆顶就和父节点交换一路往上走直到满足堆性质或者到达根节点。这个操作最多走树的高度次也就是O(logn)。下沉则用于删除堆顶或者用于建堆和堆排序的调整。以下沉为例假设当前节点不满足堆性质我们要在它的左孩子、右孩子中找到最大值大顶堆场景或最小值小顶堆场景然后和当前节点交换交换后继续向下比较直到该节点走到叶子位置或者已经满足堆性质。手写堆排序时你只需要牢牢记住下沉函数因为建堆、取堆顶、排序阶段的调整全部复用这一个函数。def sift_down(nums, n, i): # 下沉大顶堆场景n 表示当前堆的有效长度 while True: largest i left 2 * i 1 right 2 * i 2 if left n and nums[left] nums[largest]: largest left if right n and nums[right] nums[largest]: largest right if largest i: break nums[i], nums[largest] nums[largest], nums[i] i largest这里必须强调一个细节判断左右孩子下标时第一步不是比较值而是判断下标是否小于当前堆长度n。很多人写错堆排序就是因为孩子下标越界或者没有意识到“堆长度会随着排序越来越短”。一旦你把下沉函数写对了建堆和排序阶段只是换着方式调用它而已。3. 堆排序三步走建堆、交换、下沉复杂度到底怎么算3.1 建堆阶段为什么是O(n)不是O(nlogn)堆排序的第一步是建堆。如果数组已经是完全二叉树只是堆性质不满足我们要通过下沉操作把它调整成大顶堆。常规直觉是堆排序整体O(nlogn)那么建堆也应该是O(nlogn)。但真实复杂度是O(n)这几乎是面试里最高频的误区之一。为什么是O(n)关键在于每个节点下沉的代价跟它所在的层高有关。叶子节点根本不需要下沉倒数第二层的节点最多下沉1次倒数第三层最多下沉2次……越靠近根部的节点数量越少而它们需要下沉的次数越多。把每一层节点数和最大下沉次数相乘再求和最终结果收敛于一个常数乘以n而不是n乘以logn。可以做一个粗略的计算。假设树高为h根这一层有1个节点最大下沉h次下一层2个节点最大下沉(h-1)次再下一层4个节点最大下沉(h-2)次……求和S 1h 2(h-1) 4*(h-2) ... 这个等比加等差混合级数的结果趋向于2n。所以建堆阶段线性这就是为什么自底向上建堆从倒数第二层再往上一层一层调整。实现建堆时我们需要找到“最后一个非叶子节点”。在0基数组中这个节点的下标是 n // 2 - 1。因为叶子节点没有孩子不需要调整。然后从该下标递减到0逐个调用下沉函数。def build_max_heap(nums): n len(nums) for i in range(n // 2 - 1, -1, -1): sift_down(nums, n, i)这里有一个极其容易踩的坑循环必须从 n//2 - 1 递减到0不能从0递增。我从0开始递增调整过一次结果建出来的“堆”只能保证部分子树是堆整个树根和子树之间仍然可能违反堆性质排序结果自然就是错的。自底向上是堆排序铁律。3.2 排序阶段把最大值“扔”到末尾再缩小堆范围建堆完成之后大顶堆的根节点就是全局最大值。排序阶段的核心循环很直接把堆顶元素和当前堆的最后一个元素交换这样最大值就被放到了数组末尾。将堆的有效长度减1即把已经排好的元素排除在堆外。对新堆顶执行一次下沉操作恢复大顶堆性质。重复上述过程直到堆里只剩一个元素。很多第一次写堆排序的人会问不是要大顶堆吗把最大值放到末尾之后堆顶换成了一个小值这个值下沉时会不会把更大的元素再顶上来会但这正是我们想要的。第二大的节点会成为新的堆顶下一轮交换时它会被放到倒数第二个位置。这样每一轮都拿走当前未排序区间的最大值最终整个数组升序排列。把代码串起来def heap_sort(nums): n len(nums) build_max_heap(nums) for i in range(n - 1, 0, -1): nums[0], nums[i] nums[i], nums[0] sift_down(nums, i, 0) return nums注意这里sift_down的第二个参数传入的是i而不是len(nums)。因为每交换一次堆的有效长度就减少1之前放到末尾的那些最大值已经属于有序区不能再参与后续调整。这个“堆长度和数组长度不一样”的概念是堆排序最容易出bug的地方之一。3.3 完整代码和一个小例子随便拿一个数组验证一下如果输入[4, 10, 3, 5, 1]建堆后得到[10, 5, 3, 4, 1]第一轮交换堆顶10和末尾1得到[1, 5, 3, 4, 10]然后对前4个元素下沉变成[5, 4, 3, 1, 10]。第二轮交换5和1得到[1, 4, 3, 5, 10]下沉前3个元素变成[4, 1, 3, 5, 10]。第三轮交换4和3得到[3, 1, 4, 5, 10]下沉前2个元素变成[3, 1, 4, 5, 10]第四轮交换3和1得到[1, 3, 4, 5, 10]。整个排序过程完全发生在同一个数组里空间复杂度O(1)这是堆排序引以为傲的原地特性。测试时强烈建议多跑几个边界用例空数组、只有一个元素的数组、所有元素相等、包含重复元素、包含负数。尤其是所有元素相等的情况如果代码里比较符号写错很容易出现意料之外的交换虽然结果通常也是有序的但过程会多做很多无谓操作。4. 手写堆排序容易翻车的6个边界问题4.1 左右孩子下标与父节点下标必须时刻对应使用0基下标时左孩子是2i1右孩子是2i2父节点是(i-1)/2。这三个公式是堆排序的生命线。我见过有人把左孩子写成2*i还觉得没什么问题结果在数组长度为偶数时得到完全错误的结果。调试方法也很简单随意构造一个小数组在sift_down函数里打印每个节点的下标关系和交换动作一眼就能看出来是公式错了还是逻辑错了。4.2 下沉时孩子节点可能不存在必须检查下标范围堆是一棵完全二叉树但不是所有节点都有左右孩子。当i比较大时左孩子可能已经超出堆长度右孩子更可能不存在。所以在比较前必须先判断left n和right n。一个经典错误是直接访问nums[2*i1]如果越界就会抛出异常或者在语言里读到脏数据。更隐蔽的错误是在right不存在时还把nums[right]和nums[largest]比较虽然某些语言下不会报错但结果完全不可控。4.3 堆长度必须随着排序过程动态更新排序阶段每次交换后末尾元素就固定了下一轮不能再碰它。所以下沉时传入的n必须是当前堆有效长度比如循环变量i。如果你一不小心写成len(nums)已经排好的最大值又会被拉进堆里不仅做无用功还可能导致序列被重新打乱。这个问题的隐蔽性很强因为它不是必然报错而是偶尔结果正确、偶尔错误非常难以排查。建议在代码里明确写一个heap_size变量实时代表当前堆长度。4.4 相等元素和稳定性问题堆排序是不稳定排序。所谓稳定性是指值相同的元素在排序后是否保持原来的相对顺序。为什么不稳定因为在排序过程中元素会跨越很长距离交换比如堆顶和堆尾这种“远距离搬迁”会打乱相同元素的先后顺序。举个例子数组[2a, 1, 2b]用下标区分两个值相等的2建堆后2a和2b的位置可能已经交换最终输出并不保证先出现2a再出现2b。如果业务中需要稳定排序应该选择归并排序或插入排序而不是堆排序。4.5 建堆顺序从最后一个非叶子节点倒着处理前面我已经强调过建堆必须从n//2 - 1递减到0。从0递增的错误在于当调整根节点时它下沉后可能会打破已经处理过的某个子树。比如根节点比右孩子小交换后新的右子节点可能又比右子子树里的节点小但此时右子树已经错过调整时机整个堆性质依然不成立。自底向上建堆则能保证每次下沉时左右子树都已经是合法的堆所以只要把当前节点下沉到正确位置整棵子树就满足堆性质了。4.6 递归和迭代的实现选择sift_down既可以递归也可以迭代。递归版本很简洁但每次调用会产生函数栈开销虽然堆高只有O(logn)通常不会栈溢出但在追求性能或处理超大数据量时迭代版本更稳妥。更重要的是递归版本容易让人忽略“交换后要继续向下检查”这一步。如果只交换一次就直接返回那堆调整就只完成了一半排序结果必然是错的。我建议初学阶段先写迭代版本把循环写稳以后再改成递归也不迟。5. 堆排序的真实定位TopK和优先队列里它才是主角5.1 TopK问题堆是无可替代的常客如果你只需要从海量数据里挑出最大的10个数而数据量大到无法一次性全部载入内存堆排序的选择性调整能力就体现出来了。维护一个大小为10的小顶堆依次扫描数据每一轮最多做一次堆顶替换和下沉时间复杂度为O(nlogK)。K通常是几十、几百复杂度几乎可以看成O(n)。这种场景下快速排序反而不好办因为快速排序需要把整个数组都读进来才能排序。类似的场景还有合并K个有序链表、滑动窗口最大值、数据流中位数。中位数问题通常用两个堆实现一个大顶堆存放较小的一半一个小顶堆存放较大的一半保持两边元素数量差不超过1。这些题目表面上是数据结构题内核全都在考堆的维护和堆排序的下沉、上浮操作。5.2 堆排序作为通用排序的短板缓存局部性和常数因子既然堆排序复杂度稳定、空间原地为什么标准库默认排序不用它答案是常数因子和缓存局部性。堆排序的访问模式像“跳楼梯”当前节点和它的孩子可能在数组里相距很远交换完之后还要跳去访问再下一层的孩子。CPU缓存对连续内存访问非常友好而堆排序这种跳跃式的访问容易反复没命中缓存。相比之下快速排序是分块分区处理归并排序虽然是额外空间也能按连续片段读写缓存命中率要好看得多。实际跑数据时堆排序在随机整数数组上通常比快速排序慢两到三倍这还没有计算递归或函数调用的开销。所以在通用排序库的实现里你几乎见不到单纯堆排序Java的Arrays.sort对基本类型使用双轴快速排序对对象使用TimSortC的std::sort则通常使用内省排序快排递归深度过深时切回堆排序来避免最坏情况。5.3 堆排序、快速排序、归并排序怎么选维度堆排序快速排序归并排序平均时间复杂度O(nlogn)O(nlogn)O(nlogn)最坏时间复杂度O(nlogn)O(n^2)O(nlogn)额外空间O(1)O(logn)递归栈O(n)稳定性不稳定不稳定稳定缓存友好度较低高中高核心场景TopK、优先队列通用排序链表排序、外部排序这张表能回答大多数“为什么这个场景不用堆排序”的问题。如果你明确要求原地、稳定堆排序做不到稳定如果你要快堆排序常数大但如果你要处理动态数据、随时取最大值堆排序是不二之选。所以看待堆排序的正确姿势是它是一个优秀的“优先级管理”工具而不是一个“通用数组整理”工具。5.4 标准库有堆为什么还要能手写很多语言已经提供了现成的堆实现比如Python的heapqJava的PriorityQueueC的priority_queue。日常工程开发里直接调库是最稳妥的选择。那为什么我仍然建议你手写一方面面试经常让你实现堆排序或堆结构调库等于零分另一方面调库只是黑盒你迟早会遇到需要自定义堆调整逻辑的时刻。比如Dijkstra算法里用索引堆优化需要动态修改某个节点的优先级标准库的优先队列做不到高效修改这时你必须理解堆的内部结构才能手工实现索引堆。6. 从堆排序到算法思维一些不成熟的实战建议6.1 闭卷手写堆排序的考场技巧如果你正在准备面试我建议把堆排序的代码分成三个记忆块sift_down下沉、build_max_heap建堆、heap_sort排序循环。核心记忆点是下沉函数的不变量调用它之后以传入节点为根的子树必须重新满足堆性质。只要把这个不变量刻在脑子里不管你从哪个数据规模开始写都不容易跑偏。书写顺序上先写sift_down再写建堆最后写排序循环。这样写的好处是每步都能独立验证只跑sift_down可以检查它是否把子树调整正确只跑建堆可以打印整个数组看是否符合大顶堆最后再跑完整排序。此外写完代码后一定要手动跑一个长度为3到5的数组展开成完全二叉树画出来对照数组检查每一轮交换后的状态。这样做上三遍基本就不会再忘了。6.2 堆排序教给我的不只是排序我个人在实际项目里直接调用堆排序的场景其实很少但“堆”这个数据结构几乎每天都在用。任务队列根据权重调度直接用优先队列电商推荐需要实时取点击率最高的商品也是堆结构。我越来越觉得堆排序最大的价值不是让你多掌握一种排序手段而是让你建立一种“局部有序即可”的思维与其每次把全部数据整理得干干净净不如维护一个始终能快速取出最大值的结构。系统里很多性能问题本质上都是因为“过度排序”比如为了取最大值把整个数组排好序白白花了O(nlogn)如果换成堆只要O(n)建堆和O(1)取顶。如果你以后要深入数据结构的变体堆这条路还能继续往下走索引堆、二项堆、斐波那契堆、左式堆、配对堆每一层都建立在“堆性质”这个地基上。但无论变体多复杂最底层的思想仍然是这里讲的“一棵完全二叉树、两种调整动作、一个堆顶”。先把这篇里的数组下标和下沉函数吃透再去看那些高阶堆你会发现它们其实就是同一棵树的远房亲戚没什么神秘的。