排序)
★ FEATURED ARTICLE 1. 排序之前的底层逻辑堆这个数据结构到底在干什么堆排序是我在面试和学习排序算法时反复接触的一个经典算法。不管你是刚学数据结构的初学者还是已经在业务里处理过大量排序需求的老手堆排序都有值得被重新认识的价值它最吸引人的地方在于无论原始数据是顺序、逆序还是乱序都能稳定落在 O(n log n) 的时间复杂度上而且不需要额外的大块临时数组原地操作就能完成。这篇文章会从堆的定义开始把堆排序的建堆、交换、下沉每一环都拆开讲透再配上可直接落地的代码和踩坑记录希望能让你在真正写业务代码时也敢用、会用堆排序。很多人一开始背堆排序的步骤都能背出来先建堆再逐个把堆顶弹到数组末尾。但一旦自己动手写就很容易卡在“为什么最后一个非叶节点是 n/2 - 1”“为什么交换后还要重新下沉”“用最大堆还是最小堆”这些细节上。这些问题不是小问题它们直接决定你写出来的是能跑的排序还是一个死循环或越界崩溃的 bug。所以这一章先把数据结构本身讲明白不急着写排序过程。1.1 堆不是“排好序的数组”而是一棵有约束的完全二叉树堆本质上是一个数组但这个数组被我们脑补成了一棵完全二叉树。所谓完全二叉树指的是除了最后一层每一层都是满的最后一层的节点也都集中在左侧。用数组存这棵树时不需要任何指针因为父子关系可以用下标直接算出来下标为 i 的节点它的左孩子下标是 2i 1右孩子下标是 2i 2父节点下标是 (i-1)/2。这种紧凑的存储方式让堆可以做到真正的原地排序这是很多其他树形结构做不到的。最大堆还有一个额外约束每个节点的值都必须大于等于它左右孩子的值。注意这里没有约束左孩子和右孩子之间的大小关系也没有说左子树里的所有节点一定都小于右子树里的节点。换句话说堆只保证“局部父大子小”这条河流方向不保证同层节点之间的具体顺序。这也就是为什么堆不是一个“完全有序”的结构它更像公司里的职级关系总经理坐在最上面下面各层经理逐级向下但同一层员工之间谁坐左边谁坐右边没有硬性规定。用最大堆举一个具体例子[50, 30, 40, 10, 20, 35, 38, 5, 8, 15]把下标对应成树50 是根30 和 40 是它的两个子节点30 下面有 10 和 2040 下面有 35 和 3810 下面是 5 和 820 下面是 15。检查每一条父大于子的关系都成立50 30 且 50 4030 10 且 30 2040 35 且 40 38。这就是一个合法最大堆。虽然 30 那一整棵子树都比根小但右子树里的 40、35、38 这些元素并不都比左子树元素大这完全没关系。理解了这一点你就能明白为什么堆排序不需要非要递归到最细粒度去比较所有元素对。它利用的是“根是全局最大值”这个结论只要堆顶还在它一定是当前堆里最大的元素。于是排序就变成了一个连续“摘果子”的过程每次把最大的果子摘掉放在数组末尾再维护剩下的堆。1.2 两个核心动作下沉与上浮维护堆性质的动作只有两个下沉和上浮。下沉sift down的场景是某个节点违反了“父大于子”的规则。通常发生在堆顶被替换成一个较小的值之后或者在建堆过程中某个父节点比它的某个孩子小。这时候我们需要把这个节点往下移动依次和左右孩子比较选出较大的那个孩子如果它比当前节点大就交换位置然后继续在新的位置上重复这个过程直到当前节点比它的所有孩子都大或者已经到叶子节点为止。上浮sift up的场景则相反某个节点违反了规则但问题出在它可能比自己的父节点大。通常发生在向堆里插入一个新元素时新元素先放在数组末尾然后不断和父节点比较如果比父节点大就交换一路向上走直到它不高于父节点为止。堆排序用下沉比用上浮更多。原因后面在实现部分讲但你要先记住一个关键点要实现“取出最大元素后再恢复堆”最佳动作是下沉因为根节点一旦被移除或替换破坏堆性质的通常是新放到堆顶的那个值太小它需要往下找自己的位置。下沉和上浮的复杂度都是树的高度。因为二叉堆是满二叉树节点数 n 和高度 h 之间满足 h O(log n)所以单次下沉或上浮是 O(log n)。这个结论很朴素但正是堆排序能够保持 O(n log n) 的根基。1.3 为什么要费劲维护堆性质排序的本质是把无序变成有序而堆性质这个中间状态看起来“既不是有序数组也不是一棵完全排序的树”维护它到底图什么答案是为了用尽量少的比较次数拿到当前最大元素。生活里类比一下就是你不需要把所有人按年龄从大到小排成一条长队你只需要知道“谁是年龄最大的人”。堆这种结构用额外的约束换来了一个非常高的查询效率查询最大值永远只看根节点O(1) 时间。而如果要打乱这个最大值只需要一次下沉就能重新确定新的最大值O(log n) 时间。这让我想起了很多线下活动里的“分组最高个儿”场景。组织者不要求每组内部按身高站好只要求每组最高的那个人站在最前面。等真正要用最高的人时直接看最前面就行。一旦这个人被请走再从剩下的组员里重新选一个最高的补到前面。堆做的事情本质上就是这样只不过它把“组”组织成了一棵完全二叉树并且保证了每个子树的最高的节点都在子树顶端这样全局最高的自然就在整棵树的顶端。堆排序的“反复取最大值”策略也因此不需要像选择排序那样每次为了找一个最小值而扫描整个剩余数组。2. 堆排序的完整思路拆解从建堆到排序这一章我们把排序过程拆到最小步骤。堆排序的流程如果用一句话概括就是先让整个数组变成一个合法的最大堆然后反复把堆顶元素和当前堆的最后一个元素交换缩小堆的范围再让新的堆顶下沉归位。这句话看起来很短但里面藏着三个关键细节。第一“让整个数组成为合法最大堆”不是一步就能做到的它需要从最后一个非叶节点开始倒着下沉。第二“堆顶元素和最后一个元素交换”不是无脑交换每交换一次堆的有效长度就要减一否则已经排好的末尾元素会被再次卷进堆里。第三“新的堆顶下沉”不是使用原来的整棵树而是只在一个缩小的堆内下沉。这三个细节任何一个搞错结果都不是“排序慢一点”的问题而是直接输出错误结果。2.1 建堆过程从最后一个非叶节点开始倒着下沉给定一个无序数组如何把它变成最大堆朴素的想法是从头到尾遍历每个节点调用下沉或上浮。但这里有一个更聪明的做法从数组末尾往前找到最后一个非叶节点然后逐个下沉。最后一个非叶节点是哪个对于一个长度为 n 的数组最后一个元素下标是 n-1它的父节点下标是 (n-1-1)/2也就是 (n-2)/2整数除法下等同于 n/2 - 1。这个节点位于树的最低非叶子层。从这个节点开始下标依次减一一直处理到根节点。为什么从它开始因为叶子节点本身没有孩子下沉无从谈起也不需要维护性质。如果把所有叶子节点都跳过只处理有孩子的节点就能避免大量无效比较。从最后一个非叶节点开始往前处理还有一个很重要的原因每一层的节点在下沉时它的左右子树已经分别满足堆性质。因为我们在处理下标较大的节点时必然先处理了更靠后的节点。对于下标为 i 的节点来说它的左右子树根节点下标是 2i1 和 2i2都大于 i在倒着遍历的顺序中它们已经被处理过了。这样当前节点只需要把自己和已经合法的两个孩子“对整齐”就行。这种自底向上的建堆方式是堆排序性能好的关键之一。建堆完成后根节点一定是全局最大值。这一步的正确性可以用数学归纳法理解叶子节点都是合法堆然后上一层节点经过下沉后以它为根的子树也成为合法堆逐层向上最后整个数组成为一个合法最大堆。2.2 排序阶段交换堆顶与末尾缩小区间再下沉建堆之后数组里的最大元素已经在下标 0 的位置。我们要做的是把它放到最终该待的位置也就是数组的最后一位。于是第一轮排序是这样的把 arr[0] 和 arr[n-1] 交换。交换后最大元素去了数组末尾这个位置不会再参与后续调整我们可以用一个变量记录“堆的有效边界”初始值为 n每轮交换后减一。现在堆顶是原来末尾的那个小元素它大概率不满足最大堆性质所以从堆顶开始做一次下沉下沉时只在有效边界范围 [0, 当前边界) 内比较孩子。这一步做完后堆顶又是剩余元素里的最大值。然后重复这个循环交换堆顶和当前有效区间的最后一个元素边界减一堆顶下沉。直到边界变成 1剩下的一个元素自然最小排序结束。这个过程本质上和选择排序非常像每轮都选择一个当前范围内的最大值放到正确位置。但区别在于选择排序找最大值需要扫描整个数组 O(n)而堆排序通过堆结构把找最大值和恢复结构的代价都控制到了 O(log n)所以总代价从 O(n^2) 降到了 O(n log n)。如果你理解过选择排序再看堆排序思路会顺很多它就是一个“使用堆来优化查找最大值”的选择排序。2.3 为什么用最大堆升序而不是用最小堆升序很多人会问升序排列不是应该从小到大吗为什么不用最小堆每次拿最小值这里要理清楚堆排序的原地策略。最大堆的根是最大值把最大值和数组末尾交换最大值被固定在末尾。下一次最大值再去固定到倒数第二个位置。整个过程把大的元素从后往前依次放好最终得到升序数组。如果用最小堆根是最小值你需要把最小值放到数组开头。可是数组开头的位置原本是堆顶如果直接交换这个最小值确实到开头了但被交换到堆顶的那个元素可能是任意一个比较大的值你还能继续把它当堆吗可以但后续处理就很别扭为了让最小值依次放到前面你需要不断缩小“待放置前缀”的范围同时还要处理堆空间的起始位置不断前移的问题实现起来远比最大堆麻烦而且很难做到真正原地。所以常规堆排序升序老老实实用最大堆。反之如果你想做降序排序倒是可以反过来用最小堆把最小值往末尾放或者直接建最小堆然后把最大值往末尾交换那样方向又反了。最舒服的映射就是升序配最大堆降序配最小堆。2.4 建堆的复杂度为什么是 O(n) 而不是 O(n log n)单独看每个节点的下沉操作单次是 O(log n)那 n 个节点岂不是 O(n log n)这个直觉是对的但忽略了每个节点下沉的深度并不相同越底层的节点下沉路径越短甚至不到 log n 层。可以做一个简化计算。对于一个高度为 h 的完全二叉树从根到叶子不同层节点下沉的最大深度不同。假设第 k 层节点需要下沉的最大深度大约是 h - k。第 k 层的节点数大约是 2^k总代价近似求和sum_{k0}^{h} 2^k * (h - k)这个求和的结果收敛到 O(n)而不是 O(n log n)。更直观的理解是建堆过程中大量节点集中在靠近底部的层次而这些节点下沉距离很短只有少数靠近根部的节点下沉较深但它们数量少。所以平均下来每个节点只需要常数级别的比较和交换整体建堆就是 O(n)。这个结论让堆排序的总复杂度能保持在 O(n log n)建堆 O(n)后面 n 次下沉每次 O(log n)合计 O(n log n)。3. 手把手实现代码细节和边界条件堆排序的代码实现有很多种口味有些人喜欢递归下沉有些人喜欢迭代下沉有些人喜欢把建堆和排序分开成两个函数。我的建议是排序函数和下沉函数分开写下沉函数用迭代循环不要用递归。这样既方便单测也能避免在数据量大时出现递归栈过深的问题。下面给出一个 Python 版本思路是通用于任何语言的你甚至可以照着翻译成 Java、C、Go。代码里的关键点我会逐行解释。3.1 Python 实现与逐行说明def sift_down(arr, i, size): while True: largest i left 2 * i 1 right 2 * i 2 if left size and arr[left] arr[largest]: largest left if right size and arr[right] arr[largest]: largest right if largest i: break arr[i], arr[largest] arr[largest], arr[i] i largest def heap_sort(arr): n len(arr) # 1. 建堆 for i in range(n // 2 - 1, -1, -1): sift_down(arr, i, n) # 2. 排序 for end in range(n - 1, 0, -1): arr[0], arr[end] arr[end], arr[0] sift_down(arr, 0, end) return arrsift_down 函数的输入有三个arr 是数组i 是当前需要下沉的节点下标size 是当前堆的有效边界。这里 size 特别重要因为排序过程中数组末尾已经放了排好的最大元素它们不应该再参与堆调整。下沉函数的 while True 循环里先假设当前节点就是最大节点然后分别看左孩子和右孩子是否在有效范围内。注意left size和right size这两个条件不能丢。当节点位于堆的最后一层附近时它可能只有一个左孩子或者两个孩子都不存在。如果忘了判断你就会访问到数组越界之外的内存或者把已经固定到末尾的元素又拉进比较。左右两个孩子的比较顺序不敏感但逻辑要正确。先比较左孩子和当前节点的最大值再比较右孩子最终 largest 记录的是三者中最大值的下标。如果 largest 仍然是 i说明当前节点已经比它的两个孩子都大它不需要再下沉循环直接 break。否则交换当前节点和 largest 节点并把 i 更新为 largest继续处理下一层。heap_sort 函数先处理特殊情况数组长度是 0 或 1 时建堆循环里的 range(n//2 - 1, -1, -1) 分别是 range(-1, -1, -1) 和 range(0, -1, -1)都不会真的进入循环体。所以不需要额外判空代码能直接返回原数组。这是把边界写对之后的自然效果。建堆循环从 n // 2 - 1 开始到 -1 结束step 是 -1。这是为了从最后一个非叶节点开始一路下沉到根节点。排序循环从 end n-1 开始每次把堆顶和当前末尾交换后堆的有效大小变成 end然后对新的堆顶做下沉。3.2 为什么建堆用下沉而不是用上浮有一种常见的实现方式是对每个元素调用 insert 操作把新元素放到数组末尾再上浮这种办法也能建出合法堆但效率不如从后往前下沉。原因在于从后往前下沉只需要处理非叶节点而且随着从底向上逐层处理下层子堆已经合法上层节点只需要一条向下的路径就能就位。而逐个插入上浮的办法每次插入都要一次上浮而且每次插入时已经构造出来的堆规模越来越大总的比较次数会接近 n log n。从常数角度看前者也比后者少很多无效操作。堆排序既然已经以“稳定 O(n log n)”为卖点建堆可不能稀里糊涂写成 O(n log n)那会让整体常数变大。所以你在写业务代码时如果遇到需要自己实现堆请优先写下沉函数。上浮函数只在需要支持“往堆里插入一个新元素”时才必需。3.3 边界条件与索引细节从 0 还是 1 开始索引这个坑值得单独拿出来讲。很多数据结构和算法教材在讲堆时为了方便把根节点放在下标 1左孩子是 2i右孩子是 2i1父节点是 i/2。这种写法在数学推导上很干净但到了实际编程语言里数组下标通常从 0 开始。如果你从下标 1 开始存储数组首元素 arr[0] 会被当作哨兵位浪费掉而且最后排序后返回的数组还得整体前移一位。更常见的问题是你在网上看了很多资料有的从 1 开始有的从 0 开始代码没改就提交结果直接数组越界。我的建议是代码统一使用 0 下标对应关系为左孩子2 * i 1右孩子2 * i 2父节点(i - 1) // 2最后一个非叶节点n // 2 - 1这套公式是各种边界条件的基础。你可以用一个小数组手推一遍比如 n5最后一个非叶节点下标就是 2对应数组第二个元素n6 时最后一个非叶节点下标也是 2因为下标 2 是下标 5 的父节点。算错了这一项建堆就漏节点。另外排序阶段下沉函数的 size 参数要格外小心。例如 end n-1 时交换堆顶和 arr[n-1]再调用 sift_down(arr, 0, n-1)意思是有效堆只包含下标 0 到 n-2。此时如果某个节点访问 left 2*i1刚好等于 n-1但由于 left size 的判断这个已经排定的元素不会被访问。这个边界条件在递归写法里尤其容易写错因为递归进入下一次时如果 size 没有传下去子调用会继续处理已经排完的元素。4. 复杂度、稳定性与性能陷阱算法课最爱的考法就是问堆排序时间复杂度和稳定性但真正到了工程里比复杂度更值得关心的是常数、缓存和特殊情况。这一章把这一摊子事分开讲清楚。4.1 时间复杂度表不要再被最好最坏平均绕晕堆排序的时间复杂度是三种输入情况下高度稳定的情况时间复杂度原因最好情况O(n log n)即使数组已经有序排序阶段每轮仍要下沉无法跳过最坏情况O(n log n)每轮下沉最多走完树高平均情况O(n log n)数据分布不影响总轮数只影响交换次数常数空间复杂度是 O(1)因为所有操作都在原数组上进行只有几个临时变量。注意“原地”不等于“不使用栈空间”如果你用递归下沉递归调用会占 O(log n) 或者 O(n) 栈空间取决于实现。因此我前面强调迭代下沉就是想把空间复杂度真正压到 O(1)。C 或 Go 里如果你开了臃肿的递归碰到十几万级别的数据栈爆掉是非常快的。稳定性方面堆排序是不稳定的。举个例子数组 [3a, 3b, 1]建堆后可能变成 [3a, 3b, 1]排序阶段根和末尾交换后变成 [1, 3b, 3a]两个相等的 3 相对顺序就变了。只要交换堆顶到末尾这个过程存在相等元素的相对位置就可能被打乱。所以稳定排序需求面前别选堆排序。需要稳定排序时用归并排序或者常配合稳定分区的其他算法。4.2 复杂度低但常数不小堆排序为什么不一定比快速排序快很多人一开始很惊讶堆排序看起来这么优雅时间复杂度也这么漂亮为什么实际跑起来经常打不过快速排序关键在缓存和跳跃访问。快速排序的局部性很好它不断把数组切分成块递归处理子块每次比较都集中在一小块连续内存上。堆排序则不同下沉过程中父节点在 i左孩子在 2i1右孩子在 2i2随着 i 往下走访问的下标可能瞬间跳到数组的远距离区域比如根节点的孩子在下标 1 和 2但再往下一层跳到 3、4、5、6数据分布虽然不是完全随机但范围跨度很大。CPU 缓存命中率比快速排序低所以数据量一大堆排序的“理论优势”会被内存访问开销抵消一部分。还有一点堆排序的交换次数在实际数据上并不少。最坏情况下每个下沉操作都可能一路交换到叶子即使数据已经比较有序堆顶被替换后依然要从根走到叶子附近。快速排序如果遇到近乎有序的数据配合好的分区策略和插入排序兜底能很快收敛。堆排序却没有这种“自适应”能力它像一个严格执行排名的管理者不管团队已经稳定得多好每次换上临时负责人都要重新梳理全队。这不代表堆排序没用。它的优点是最坏复杂度严格保证不像快速排序那样依赖枢纽选择不需要额外内存没有递归导致栈溢出的风险实现逻辑固定。在嵌入式环境、对最坏延迟敏感的系统或者内存极其受限的场景里堆排序可靠得像老黄牛。4.3 两个值得了解的优化思路虽然基本堆排序已经足够教学用但如果你想把它推向更好的实际性能有几个常见优化方向。第一个是“先比较后交换”的优化。下沉操作里每一步都交换父节点和孩子节点会带来大量赋值操作。你可以先把当前节点 i 的值缓存到一个临时变量里然后沿较大孩子的方向一路找下去把“空位”向下移直到找到正确位置最后把临时变量一次性写入。这类似于插入排序里的移位式写法能明显减少数组写操作。第二个是处理相同元素较多的情况。堆排序对大量重复元素不够友好因为孩子等于父节点时我们通常选择不交换但有些实现会因为比较细节导致不必要的抖动。你可以考虑维护两个哨兵或者引入分区思想不过这些优化会让代码复杂度上升。现实项目中如果数据重复度高优先考虑三路快速排序或计数排序而不是堆排序。5. 常见问题与实战经验这一章我把自己写堆排序和看别人写堆排序时遇到的高频 bug 整理成速查表再聊一聊堆排序在排序之外的应用比如 TopK 问题和优先级队列。最后的实战心得是我自己的体验适合你看完代码后再对照着验证。5.1 高频错误速查表错误类型典型表现解决思路建堆起点错误小数组排序结果不对部分元素没参与堆化检查是否用了 n//2 - 1 而不是 n//2 或 n-1下沉访问越界运行时数组下标越界检查 left size 和 right size交换后堆范围没缩小排序后末尾元素又被调整确保每轮 end 减一递归下沉但 size 没传对已排序部分被再次堆化下沉函数必须带 size 参数误用最小堆结果降序而不是升序升序最大堆降序最小堆数组为空或长度 1某些写法直接进入循环导致错误确认 range 的 start 和 stop 关系最容易栽的是数组越界。比如你写了下沉函数但只检查左边孩子右边孩子不检查或者两边都不检查只要堆不是满树就很可能访问到数组外。检查条件必须同时覆盖左孩子和右孩子。死循环也常出现。一种情况是下沉函数里没有 break 条件或者 break 条件写得不对导致一直在同一个位置交换。另一种情况是在交换后没有更新 i只原地反复交换。正确做法是交换完把 i 更新为 largest继续下一层比较。5.2 排序之外的延伸优先队列与 TopK堆排序的底层数据结构本身就值钱。Java 里的 PriorityQueue、Python 里的 heapq 模块、C 里的 priority_queue底层实现都是堆。你掌握了堆排序其实也掌握了这些优先队列的构造和调整逻辑。实战中我很常用到一个思路求一个大数据流里的 TopK 元素不需要把所有数据都排序。维护一个大小固定为 K 的最小堆新元素进来时如果比堆顶大就替换堆顶并下沉这样堆里始终是最大的 K 个元素复杂度是 O(n log K)。这个方法在内存有限、数据量巨大的场景下非常好用。你可以把它看作堆排序的逆操作堆排序不断把最大元素移到末尾而 TopK 方法通过小堆把“门槛”压在堆顶不断淘汰低分。另一个常用场景是合并多个有序数组也就是多路归并。维护一个堆里面每个元素代表一路数组的当前值每次从堆顶取出最小值再从对应数组推入下一个值最终就能合并成全局有序。这个算法在外部排序和数据库执行计划中很常见堆同样是核心角色。5.3 什么时候该选堆排序选排序算法不能只看时间复杂度表格更得看场景。快速排序一般是最泛用的内存排序首选但在最坏时间复杂度敏感的场景里它需要小心处理。归并排序稳定且适合链表和外部排序但需要额外空间。堆排序则适合内存受限不能多开一块大数组对最坏情况延迟有硬性要求需要稳定 O(n log n)业务逻辑里本来就要维护最大堆或最小堆结构嵌入式或低级环境递归栈深度不可控需要增量排序或优先队列语义如果只是给一个普通数组排序数据规模不大我又没有特殊稳定性要求我通常还是会直接用快速排序因为它的平均常数小实现也成熟。但如果是写一个实时数据流处理模块需要反复获取当前最大元素那堆这个结构几乎是不可替代的。5.4 实测记录与最后的心得我在本地做过一些不同数据规模下的对比实验想测测堆排序和快速排序的差距。随机整数数组规模在十万量级时堆排序通常比快速排序慢差多少取决于语言和实现有时能慢 1.5 到 2 倍。把数组改成几乎有序的输入时快速排序配合切分优化会更有优势堆排序的速度基本不变。但一旦把场景改成“内存只有原始数组大小不允许额外空间”堆排序的优点就完全压过快速排序了因为快速排序的递归和分区需要栈空间递归深了也一样有风险。还有一次我在某个项目里需要同时对两个关键字段做排序展示最初用了堆排序做排序逻辑后来测试发现稳定性不符合产品需求相同排名字段的内容顺序出现了跳跃。那次之后我把稳定性判断提到了选型最前面。堆排序本身没有错只是它满足不了这个特定需求。这件事给我的启发是排序算法不是背几个复杂度结论就能用好的你必须在真实场景里关心常数、稳定性和边界行为。最后再分享一个小技巧写堆排序时不要先用大数组测试先用长度 0、1、2、3、4、5 的小数组分别验证再上随机大数组。长度 2 的用例尤其能暴露“最后一个非叶节点算错”的问题长度 3 能暴露左右孩子比较时越界的问题。等你把这几组小用例跑通再进入 10 万级随机数验证和与标准库排序结果的比对心里就会踏实很多。算法这种东西靠理解远胜过靠背把小例子手推一遍比看十遍代码都管用。
阅读完成 · 觉得有帮助？
