堆排序这块内容我在不同阶段反复接触过好几轮最早是大学数据结构课后来是准备某公司的面试题最近则是帮某个模拟项目做大数据量排序优化时又把它捡起来。每次重新看它都有新的体会这次干脆把整个堆排序彻底拆一遍从原理到实现再到避坑一次性讲清楚。没有接触过堆的朋友也不用慌这篇文章我会尽量用能听懂的大白话把“堆”这个概念讲透再带你手写一版能直接用的堆排序代码。学完之后你不仅能回答“堆排序时间复杂度是多少”这种面试题还能在处理Top K、优先级队列这类问题时主动想到用堆来搞定。如果你正在复习数据结构、准备机试或者面试算法题这篇文章应该能帮你省不少时间。1. 堆排序整体设计与思路拆解1.1 先搞清楚“堆”是个什么结构堆排序的核心不是排序本身而是“堆”这种数据结构。我们常说的堆本质上是一棵完全二叉树并且要满足一个特殊的大小关系大顶堆是每个父节点都大于等于它的子节点小顶堆是每个父节点都小于等于它的子节点。完全二叉树这个概念很多人会把它理解成“除了最后一层其他层都排满”其实严格来说最后一层节点要靠左排列。堆之所以用完全二叉树是因为它有一个其他树结构给不了的好处完全二叉树天然适合用数组来存每个节点的位置和它的父子关系可以直接用下标计算不需要额外的指针。这正是堆排序能实现原地排序、不需要额外内存的关键前提。我遇到过不少朋友把堆和“堆栈”里的堆搞混在内存模型里堆是动态分配内存的区域和这里的数据结构完全是两码事。数据结构里的堆你就把它想成一个“有规则的二叉树队列”就好它更像是一个随手可以取到最大或最小元素的容器。1.2 堆排序的核心思路怎么把无序数组变成堆堆排序的整体思想可以用一句话概括先把整个数组调整成一个大顶堆让堆顶元素是最大值然后把堆顶和最后一个元素交换最大值就归位到数组末尾了。接下来把剩下的元素重新调整成堆再取堆顶、再交换……反复执行直到整个数组有序。这个过程有点像你面前有一堆乱放的积木你先花力气把它们堆成一个规整的金字塔尖最上面那块永远是最大的。你把它取走放到旁边的收藏盒里剩下的再重新整理成金字塔再次取走最大的。每次整理和取走都会让工作区域越来越小最后积木全部按从大到小的顺序进了收藏盒。这个思路里最关键的一步就是“调整成堆”技术上叫“堆化”。堆化有两种方向一种是向下调整把某个不合法的父节点往下沉直到满足堆的性质另一种是向上调整把新插入的节点往上冒泡。堆排序建堆和排序阶段主要使用向下调整理解透彻这一操作比死记代码重要得多。1.3 时间复杂度为什么稳定是O(nlogn)堆排序最大的优点之一就是时间性能相当稳定。建堆阶段的时间复杂度是O(n)这也许和很多人直觉不一样觉得建堆要把每个节点都调整一遍应该是O(nlogn)但实际上简单分析一下就会明白每个节点下沉的代价和它的高度有关越靠近叶子的节点下沉次数越少把所有代价累加起来是个线性级别。排序阶段要执行n-1次交换每次交换后需要从堆顶向下调整一次调整代价是O(logn)所以合并后整体是O(nlogn)。这个稳定性的意义在于不管输入数据是已经完全有序、完全逆序还是随机分布堆排序始终都能跑出差不多的性能表现不像快排在极端情况下会退化到O(n^2)。当然“稳定”指的是时间复杂度的稳定它不保证排序算法本身的稳定性顺序相同的元素可能会互换位置这一点我之后会在常见问题部分详细说。2. 核心细节解析与实操要点2.1 数组下标和树结构的一一对应关系堆用数组存储时下标之间的关系是必须背熟的地基。如果数组下标从0开始那么对于下标为i的节点它的左孩子是2i1右孩子是2i2它的父节点是(i-1)/2向下取整。这个关系一旦记错后面所有代码都会跑偏。我这里提供一个非常直观的验证方式你随便拿一个数组比如[4, 10, 3, 5, 1]把下标写上去然后画出对应的完全二叉树把每条弧线上的父子下标关系逐个验证一遍。我刚开始学习的时候就在纸上画了好几个例子直到自己能随口说出任意下标的孩子和父节点位置才算是真正掌握了。这里有一个小坑需要特别说明如果使用从1开始的下标公式会变成左孩子2i、右孩子2i1、父节点i/2。我们在机器考试或者用C语言写代码时习惯从0开始所以我后面所有代码统一采用0开始的写法。你在看别人代码时一定先看清是几开始的下标不然照搬很容易出边界错误。2.2 向下调整到底在做什么向下调整函数通常叫siftDown或者heapify。它的作用是这样的在某个范围内假设只有下标为start的节点不可靠它的左右子树都已经是合法的堆此时我们要把start节点不断往下移动直到它和当前子树的所有后代都满足堆的大小关系。具体操作是从start节点开始每次找到它和左右孩子中最大的孩子比较。如果当前节点已经比孩子都大说明堆的性质已经满足直接停下来。否则交换当前节点和那个最大孩子然后继续以孩子的下标作为新的当前节点重复这个过程直到越过范围边界。我把这个操作的每一步拆开写一下方便你对号入座记录当前父节点下标parent和左孩子下标child 2*parent 1。如果右孩子存在且右孩子比左孩子大就把child换成右孩子下标。比较arr[parent]和arr[child]如果父节点大于等于这个更大的孩子直接跳出循环。否则交换两者把parent更新为child重新计算child。这个函数是整个堆排序的发动机做实习项目时我曾经在笔试答卷上因为把“右孩子存在且更大”的判断写反了导致整体排序结果错得离谱排查了半天才发现是这里的问题。所以编码时要格外小心。2.3 建堆为什么从最后一个非叶子节点往前调整如果整个数组都是乱的我们不能直接从上往下调整因为没有“底下部分已经是堆”的前提。正确做法是自底向上逐层堆化从最后一个非叶子节点开始往前一直到根节点逐个执行向下调整。最后一个非叶子节点的下标是n/2 - 1这里的n是数组长度整数除法。为什么是这个值因为最后一个节点下标是n-1它的父节点是((n-1)-1)/2化简之后就是n/2 - 1。画一棵完全二叉树就会明白这个位置是所有叶子节点共同父节点中下标最大的那一个从这个位置往前调整就能保证每次执行siftDown时当前节点的左右子树都已经满足堆要求。我需要提醒一点很多人一开始会用两层循环想着每个节点都往下调整到不能再调但一定要记得循环方向是从中间往前而不是从前往后。如果从0开始向后调整后面的节点还没有完成堆化前面的调整很可能白做甚至把已经形成的局部堆关系破坏掉。2.4 排序阶段的边界条件怎么控制建堆完成之后堆顶是最大值接下来进入排序阶段。做法是交换堆顶和当前范围的最后一个元素然后范围左边界不动右边界减一在缩小的范围内重新从堆顶做一次向下调整。这个阶段最大的考点就是边界下标写得准不准确。我的建议是始终用“当前堆的最后一个下标end”来约束范围而不是靠数组长度因为数组长度不变但堆的有效范围一直在变。每轮交换之后end要减一然后调用siftDown(arr, 0, end)。循环直到end等于0为止。有次我在自己练习时把siftDown里的end传成了数组长度减一排序中途交换过的元素又被重新拉回到堆里参与调整结果整个序列又乱了。所以务必记住siftDown的第三个参数是“当前堆有效范围的最右端下标”不是数组长度。3. 实操过程与核心环节实现3.1 手写一版可以直接用的C语言实现刚开始学习时我习惯把siftDown独立出来这样堆排序的主干非常清晰。下面的实现是大顶堆排序结果是升序。为了便于对照我尽量保持变量名直白。#include stdio.h void swap(int *a, int *b) { int tmp *a; *a *b; *b tmp; } void siftDown(int arr[], int start, int end) { int parent start; int child 2 * parent 1; while (child end) { if (child 1 end arr[child] arr[child 1]) { child child 1; } if (arr[parent] arr[child]) { break; } swap(arr[parent], arr[child]); parent child; child 2 * parent 1; } } void heapSort(int arr[], int len) { for (int i len / 2 - 1; i 0; i--) { siftDown(arr, i, len - 1); } for (int i len - 1; i 0; i--) { swap(arr[0], arr[i]); siftDown(arr, 0, i - 1); } } int main() { int arr[] {7, 3, 8, 5, 1, 6, 2, 4}; int len sizeof(arr) / sizeof(arr[0]); heapSort(arr, len); for (int i 0; i len; i) { printf(%d , arr[i]); } return 0; }这段代码是一个标准的大顶堆排序基本上在任何OJ平台上都能直接提交运行。需要留意的是main函数只是为了演示实际封装时你应该把heapSort设计成接收数组和长度两个参数的通用函数不要和具体的测试程序耦合在一起。3.2 Python版实现代码少但思路完全一致对于刷题和快速验证来说Python写起来更顺手。逻辑完全一样只是语法换了。def sift_down(arr, start, end): parent start child 2 * parent 1 while child end: if child 1 end and arr[child] arr[child 1]: child 1 if arr[parent] arr[child]: break arr[parent], arr[child] arr[child], arr[parent] parent child child 2 * parent 1 def heap_sort(arr): for i in range(len(arr) // 2 - 1, -1, -1): sift_down(arr, i, len(arr) - 1) for i in range(len(arr) - 1, 0, -1): arr[0], arr[i] arr[i], arr[0] sift_down(arr, 0, i - 1)Python里交换两个值直接a, b b, a就可以不需要额外的swap函数。我在笔试的时候经常使用这个版本因为它写起来快而且变量名sift_down和C版本的siftDown对应不容易混淆。3.3 手动跑一遍排序过程加深理解只看代码常常觉得懂了实际一跑就懵。我推荐你用一个小数组手动推演一遍比如[4, 10, 3, 5, 1]。先把原始数组画成完全二叉树确认根是4左孩子10右孩子310的左孩子5和右孩子1。建堆阶段从下标1开始调整因为len5len/2-11。下标1对应元素10它的孩子5和1都比它小不需要动。然后调整下标0元素4它的两个孩子是10和3选取更大的孩子10交换交换后4到了下标1的位置继续看它的孩子5和1又和5交换最终根变成10序列变为[10, 5, 3, 4, 1]。到这里一个大顶堆就建好了。排序阶段第一步交换元素10和1数组变成[1, 5, 3, 4, 10]有效范围缩小到前4个把1从堆顶向下调整最后得到[5, 4, 3, 1, 10]。这样的过程反复进行每次确定一个最大值放到底部最后得到[1, 3, 4, 5, 10]。这样的手推不超过五次你对堆排序的执行逻辑就会非常清晰。3.4 建堆复杂度的直觉理解很多第一次接触堆排序的同学都会问建堆时明明要对接近一半的节点做调整为什么建堆复杂度是O(n)而不是O(nlogn)关键在于每层节点数量和下沉代价成反比。接近树底的节点最多但它们离叶子距离近向下调整只能走一两步。接近树根的节点数量少虽然要走很多步但数量占比太低。每一层累加起来是一个以公比小于1的等比级数求和结果是常数倍的n所以整体就是O(n)。排序阶段的n-1次调整每次是O(logn)所以总的复杂度是O(n (n-1)logn)也就是O(nlogn)。这个知识点在很多复习资料里会单独拿出来问如果你能把上面的直觉用平实的语言说出来基本上面试官就会认为你是真的理解而不是背下来的。4. 常见问题与排查技巧实录4.1 为什么大顶堆排出来是升序这个问题是我当年学习时纠结过很久的。大顶堆明明堆顶是最大值怎么排出来反而是升序关键在于排序阶段的动作每次把堆顶最大值交换到数组末尾而且是先从后往前填充。首轮把最大值放到最末尾次轮把第二大值放到倒数第二位依此类推。数组从后往前被最大值依次填充最终前面的元素自然就是最小值整体呈现升序。如果你想要降序结果可以构建小顶堆每次把最小值送到末尾最后整体就是降序。也可以继续用大顶堆在排序完成后把数组反转。前者逻辑更一致后者代码改动小具体取舍看你更看重可读性还是兼容性。4.2 堆排序稳定吗为什么不稳定堆排序是不稳定排序。要理解这个问题可以盯住交换堆顶和末尾这个动作。堆顶是全局最大值假设数组里有两个数值相同的元素其中一个恰好被交换到了末尾那么它和另一个相同数值元素的相对顺序就可能被改变。再退一步说建堆阶段的跨距离交换也可能打乱相对顺序。比如在后面有一个较小的元素在建堆过程中它可能串到前面而它本来应当排在某个相等元素之前结果变成了之后。所以不能拿堆排序去做需要保留原始顺序的排序任务比如按分数排序且同分要按学号升序这种场景堆排序做不到要选择稳定排序算法。4.3 我见过的最典型的三个Bug先说第一个也是最常见的建堆循环的下标写成了从n-1开始。这会让每个叶子节点都被单独当成根来调整实际上叶子节点没有孩子向下调整什么也不做最终整个数组根本没有建成大顶堆排序结果自然全错。第二个Bug是siftDown的结束条件写成了child len但这里的len一直没有变化。每轮排序后堆的真实右边界是i-1如果用它当成边界反复调整已经排好的元素那些已经归位的最大值又可能被换回堆里排序过程会变得乱七八糟。第三个Bug是在找较大的孩子时漏掉了右孩子越界的判断。如果当前节点只有左孩子没有右孩子直接把child自增会导致访问到错误位置。所以务必先判断child1是否在范围内再进行比较。为了更快定位问题你可以打印每一轮交换后的数组观察变化重点看最大值有没有逐步沉到末尾。如果某轮之后末尾出现非当前最大值基本可以确定是边界处理出了问题。4.4 性能上容易忽视的坑堆排序虽然时间复杂度很优秀但它的实际常数相对比较大。我在某数据处理脚本里对比过元素个数只有几千个时库函数排序往往比手写堆排序快得多堆排序要到数据量很大时才能体现出优势。所以不要觉得学了堆排序就万事大吉小规模数据直接用现成的快速排序就好。另外堆排序对缓存不友好。它访问数组的方式是不断跳跃式的尤其在建堆阶段下标之间的关系会让CPU缓存的命中率不如那些线性扫描算法。这是很多资料不会写但实测确实存在的现象工程上需要十万百万级数据排序时我会更偏好优化过的快速排序或归并排序除非有明确的求Top K需求。4.5 机试中经常出现的变形考法堆在这里不只是用来排序面试和机试更多会考Top K问题。例如从一个大数组中找到最大的K个数解法是维护一个大小为K的小顶堆每来一个元素就与堆顶比较如果比堆顶大就替换堆顶并重新堆化。这样堆顶始终是当前K个最大数中的最小值全数组扫描完堆里留下的就是最大的K个。还有一类考法是模拟优先队列比如不断给出若干任务和优先级弹出优先级最高的任务。手写小顶堆或大顶堆配合入堆时的向上调整和弹出堆顶后的向下调整就能实现一个原始但有效的优先队列。这类代码通常比堆排序更考验你对上浮和下沉两套操作的综合掌握我建议你把向上调整的代码也单独练熟面试时能减少很多思考时间。5. 堆排序的应用场景与横向对比5.1 与其他排序算法的选择策略很多人在选择排序算法时会纠结堆排序、快速排序和归并排序。我的经验是如果需要稳定排序优先归并排序如果数据量巨大且不允许额外内存空间堆排序是不错的选择因为它的空间复杂度是O(1)如果是随机数据的常规排序快速排序通常平均表现最好。堆排序还有一个独特的价值是在数组需要“边处理边排序”的场景。比如每次向数据集中增加一个新元素又要立刻取出最大值这种动态场景不是一次性的全量排序能解决的用堆维护当前最大元素效率最高。这种情况严格来说用的是堆这个结构而不是堆排序全流程但两者共享同一套核心代码。如果内存足够归并排序在稳定性上的优势无法替代。但如果只是算法考试和练习堆排序的思维难度高于快排和归并掌握之后对其他数据结构的理解也有帮助。5.2 手写堆的向上调整补充向上调整和向下调整是对称的。入堆时先把新元素追加到数组末尾然后不断与父节点比较如果大于父节点就交换直到堆顶或满足堆性质。我用C风格写一个供参考void siftUp(int arr[], int start) { int child start; int parent (child - 1) / 2; while (child 0 arr[child] arr[parent]) { swap(arr[child], arr[parent]); child parent; parent (child - 1) / 2; } }向上调整的边界是child是否大于0也就是说还没到根节点。这个操作配合siftDown可以实现一个完整的优先队列。不少同学只练排序不练入堆但实际工程里后者的使用频率更高。5.3 堆排序相关技巧的扩展思考掌握堆之后你会发现它的应用远不止排序。例如求数据流中的中位数可以维护一个大顶堆和小顶堆分别保存较小的一半和较大的一半动态调整两堆数量这样始终能在O(1)时间拿到中位数。这类问题在小红书或者面试题里经常出现本质都是堆的变式。我在实际做模拟项目时还用过堆来维护一批定时任务的最近触发时间每次取堆顶就能知道下一个要执行的任务是谁触发时间变化时直接堆化一下。比起每次扫描全表改造后效率提升了几个量级。多留意手写的堆它并不是只在课本里出现的知识点而是实实在在能解决问题的工具。最后分享一点个人的实践体会真正让我把堆排序“内化”的不是多写几遍代码而是在纸上反复画图。每次调整路径都手动标一遍观察父子节点怎么换位、边界怎么变化。画过几十个例子之后我对下标公式从生疏变成了一种条件反射。如果你正在准备机试我建议你在白纸上把上面那版C语言代码默写三遍重点关注siftDown函数的三个参数变化。多写几遍后你会发现最核心的不再是“记得代码”而是“理解堆在数组里流动的形态”。另外一个小经验是调试堆排序时打印中间状态是非常高效的排查手段。每轮结束不要只看最终结果把数组打印出来对照推演过程问题几乎立刻就能定位到是建堆阶段还是交换阶段出的错。这个习惯我保持到了现在解决过很多看似莫名其妙的问题。