堆排序在“八大排序”里一直是个很特别的存在。你说它难吧代码模板背下来也就十几行你说它简单吧很多人学完只记住了“建堆、交换、再调整”这个流程换个Top-K场景就不会用了。这篇我想换一条思路来讲不把堆排序当成一个孤立的排序算法而是从“堆结构”本身出发把堆排序和Top-K问题串成一条线。你会发现这两件事本质上用的是同一套机制——堆顶的极值、上滤下滤的调整、以及“用空间换时间”的取舍。无论你是准备面试、刷LeetCode还是工作中要处理“取前100个最大订单”“维护热搜榜Top-K”这类需求这篇文章都能给你一套可以落地的思路。1. 堆结构到底是什么数组里藏着一棵“逻辑树”很多人一听到“堆”就觉得要画二叉树、写指针其实堆的逻辑模型确实是树但物理存储上就是一个数组。这种“逻辑是树、物理是数组”的设计是堆一切优秀特性的根源。1.1 堆的数学定义完全二叉树 父大于子堆首先是一棵完全二叉树再叠加一个大小关系约束。完全二叉树意味着每一层都是满的最后一层从左到右填充这保证了树的高度稳定在 log₂(n) 量级也保证了数组存储时不会浪费空间。大小关系约束有两种大根堆Max Heap每个节点的值 ≥ 孩子的值堆顶是全局最大值。小根堆Min Heap每个节点的值 ≤ 孩子的值堆顶是全局最小值。我用一个特别朴素的例子帮我妈解释什么是堆你开了一家小卖部货架最显眼的位置永远放着最热销的商品。不管新进货还是卖了货你都会立刻把当前最好卖的东西放到第一层。堆干的就是这件事——它保证“此刻你永远知道仓库里最值钱的是哪件”代价是每次变动后要花点时间重新整理一下货架。数组下标关系是节点 i 的左孩子是 2i1右孩子是 2i2父节点是 (i-1)/2。以 0 为起点的下标体系在代码里最常见千万注意别跟 1 为起点的写法混了这是堆排序里最高频的bug来源。1.2 堆的两个核心动作上滤与下滤堆的所有操作本质上只做两件事把节点往上挪上滤sift up或者把节点往下沉下滤sift down。上滤用于插入场景。新元素先扔到数组末尾然后一路和父节点比较如果违反堆序就交换直到找到合适位置。因为完全二叉树高度是 log₂(n)所以插入的最坏时间复杂度是 O(log n)。下滤用于删除堆顶或调整场景。删除堆顶时把数组最后一个元素放到堆顶然后和左右孩子中较大大根堆/较小小根堆的那个比较如果违反堆序就交换一路下沉到正确位置。这两个动作的时间复杂度都是 O(log n)。可以说堆的所有功能——无论是排序、Top-K、优先级队列、还是中位数维护——都是这两个动作的不同组合。搞懂了上滤和下滤堆的场景题就是换皮不换里。注意下滤和上滤不是对称的。上滤只需要跟一个父节点比下滤却要同时比较两个孩子再决定跟谁换。所以下滤的代码更要注意边界条件左孩子、右孩子是否越界要判断清楚。1.3 为什么说“极值优先”是堆的灵魂堆结构和数组、链表相比最大的特点是获取极值只需要 O(1) 时间也就是直接读heap[0]。删除极值、插入新元素则是 O(log n)。这个“极值即堆顶”的特性让堆天然擅长两类事一类是“每次都要取当前最大/最小”的调度问题另一类是“只关心前几名不关心全局顺序”的选择问题。排序属于前者——每次取堆顶最大元素依次放到末尾就排好了Top-K属于后者——维护一个大小为K的堆堆顶就是第K名的门槛。你会发现两者用的是同一个堆结构只是“操作方式”略有不同堆排序把堆当“提取器”Top-K把堆当“门槛”。2. 堆排序的完整实现从建堆到有序数组堆排序整体可以拆成三大步建堆、重复提取堆顶、得到有序序列。其中建堆的细节决定了算法的时间复杂度很多人背代码但不理解为什么从 n/2 - 1 开始这一节我讲透。2.1 建堆Heapify为什么从最后一个非叶子节点往前遍历堆排序可以把数组原地变成大根堆不需要额外的空间。建堆的经典做法是 Floyd 算法从最后一个非叶子节点开始依次往前做下滤。最后一个非叶子节点的下标是 n/2 - 10-based。为什么是这个位置因为叶子节点本身没有孩子一定满足堆序不需要调整。从最后一个非叶子节点开始等于从最底层“有孩子”的节点开始逐层向上整理。void siftDown(vectorint arr, int i, int n) { 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) { swap(arr[i], arr[largest]); siftDown(arr, largest, n); // 继续向下调整防止破坏子树堆序 } } void buildMaxHeap(vectorint arr) { int n arr.size(); for (int i n / 2 - 1; i 0; --i) { siftDown(arr, i, n); } }这里为什么用递归下滤而不是循环递归写法语义更清晰但工程上建议改成迭代避免大数据量时递归栈过深。二者逻辑一样面试时写递归更快笔试时手写迭代更稳。建堆的时间复杂度是 O(n)不是很多人直觉上的 O(n log n)。直觉解释是建堆时处于低层的节点数量多但下沉路径短处于高层的节点数量少但下沉路径长加权求和后收敛为线性。严格推导需要用到“树高求和”的级数结论是 T(n) O(n)。相比之下如果一个一个地插入建堆复杂度是 O(n log n)。所以面试时被问“建堆时间复杂度”答 O(n) 才是正解。2.2 排序过程把堆顶“摘”下来把末尾“顶”上去建堆完成后堆顶就是全局最大值。排序的思路很直接把堆顶和数组末尾交换最大值就落在了最终位置然后把堆的有效范围缩小1对新堆顶做一次下滤。重复 n-1 次数组就从小到大了大根堆配合“从后往前填”的结果。void heapSort(vectorint arr) { int n arr.size(); buildMaxHeap(arr); // 第一步原地建堆 for (int i n - 1; i 0; --i) { swap(arr[0], arr[i]); // 堆顶最大值放到位置i siftDown(arr, 0, i); // 恢复前i个元素的堆序 } }注意这里siftDown的第三个参数是i表示当前堆的有效长度是i注意不要写成n。如果你用循环实现下滤循环条件要写2 * i 1 heapSize而不是2 * i 1 n。这个边界错误几乎每个人都踩过。排序阶段每次取堆顶 O(1)但每次需要下滤 O(log n)共 n-1 次所以排序阶段 O(n log n)。整体堆排序的时间复杂度最好、最坏、平均都是 O(n log n)空间复杂度 O(1)属于原地排序。2.3 稳定吗不稳定原因很直观堆排序是不稳定排序。稳定性的定义是相等元素的相对顺序排序后保持不变。堆排序的不稳定来源于“远距离交换”——堆顶和堆尾的元素可能隔着很长的距离交换时会把相同值的相对位置打乱。比如数组 [5a, 3, 5b]大根堆建好后5a 和 5b 的先后关系可能就变了因为堆调整时不是只做相邻交换。实际场景如果要保留原始顺序比如按成绩排序还要保持同分同学按学号顺序堆排序就不适用。工程里用的排序更多是快排不稳定和归并稳定这跟语言标准库的实现策略也有关C 的std::sort通常走快排std::stable_sort走归并。我自己的习惯是纯理论题、Top-K题、需要手写小规模排序时用堆排序、堆结构涉及业务数据顺序保真时宁愿多用一点空间走归并。堆排序的“O(1)空间 O(n log n)时间”听起来很美但实际性能因为局部性差常常跑不过快排这部分我在后面第5节会展开讲。3. Top-K 问题把“排序”换成“选择”Top-K 问题的经典描述是找出一组数据里最大或最小的K个元素。它和排序的区别在于Top-K 不关心全局顺序只关心“前K名”。这就让“全排序”变成了一种杀鸡用牛刀的做法。堆在这里的优势非常明显时间 O(n log K)空间 O(K)而且天然支持数据流。3.1 Top-K 三大经典问法Top-K 常见的问法有三种最大K个元素Top K largest最小K个元素Top K smallest第K大元素Kth largest是前两种的特例可以先用堆维护大小为K的“门槛”然后取堆顶。实际业务中这三种都有大量应用电商平台要展示销量最高的100个商品最大K个系统日志要找出最频繁出现的50条错误这里会先转成频次统计再按频次取最大K个推荐系统要过滤掉热度最低的200条内容最小K个。这些场景的共同点是K 远小于 n并且数据量可能很大甚至大到无法一次性装入内存。3.2 找最大K个维护一个大小为K的小根堆求最大K个元素用最短的思路是维护一个小根堆大小限制为K。遍历数组时如果堆还没满就直接入堆堆满了就与堆顶比较如果当前元素比堆顶大说明堆顶那个“排行榜最后一名”该被挤掉了弹出堆顶、把新元素放进去。vectorint topKLargest(const vectorint nums, int k) { if (k 0) return {}; priority_queueint, vectorint, greaterint minHeap; // 小根堆 for (int x : nums) { if (minHeap.size() k) { minHeap.push(x); } else if (x minHeap.top()) { minHeap.pop(); minHeap.push(x); } } vectorint res; while (!minHeap.empty()) { res.push_back(minHeap.top()); minHeap.pop(); } return res; }这里的关键点是小根堆的堆顶永远是当前K个候选里最小的那个也就是“第K名”。新元素只要比第K名大就说明有资格进入前K名顶掉第K名后重新调整。遍历完所有元素堆里留下的正好就是前K大。建议画个例子手推一遍比如数组 [3,2,1,5,6,4]K3。你会发现每次更新堆顶都是把“候选人名单”的最后一名换掉这个过程非常直观。我用这个例子给不少同学讲过几乎一遍就能听懂。复杂度上每步最多 O(log K) 一次堆调整所以总体 O(n log K)。如果K很小比如K10这个算法几乎就是 O(n)比全排序的 O(n log n) 快一个量级这也是它适合海量数据的原因。3.3 第K大元素堆解法 vs 快速选择Quick Select第K大是 Top-K 的一种特例常见解法有两个路线堆和快速选择。堆解法先建一个大小为K的小根堆过程同上最后返回堆顶即可复杂度 O(n log K)。优点是稳定不会退化而且非常好写很少出错。快速选择基于快排的 partition 思想每次确定一个 pivot 的最终位置如果这个位置正好是第K大直接返回否则递归地去某一侧继续找。平均时间复杂度 O(n)但最坏是 O(n²)比如输入已经有序且每次 partition 都选到最差的 pivot。我自己的建议是面试里被问到“第K大”先答快速选择体现你懂复杂度优化但马上补一句“不过快速选择有退化风险我会用堆作为稳定方案”。这会让面试官觉得你有复杂度敏感度又有工程意识。笔试写题、生产环境我几乎都用堆除非面试官明确要求 O(n) 平均复杂度。3.4 数据流和分布式场景堆的优势进一步放大堆解法还有一个独特优势它天然适合数据流。数据流意味着你不知道总数据量有多大甚至不知道什么时候结束。全排序必须先拿到全部数据快速选择虽然能处理静态数组但也要把数组完整读入内存。堆只需要维护K个元素的内存就能一直跑到数据流结束。举个例子你写一个日志监控系统每秒钟产生几千条日志想实时统计当前出现频次最高的10个错误码。对每条日志先用哈希表累计频次再把这个频次更新到堆里。不管是持续跑1小时还是1个月内存占用都是恒定的 O(K)。分布式场景也很类似10台机器各存了一部分数据想求全量Top-K。标准的做法是每台机器各自用堆求出局部Top-K然后把每台机器的局部结果汇总到一台机器上再对这 10×K 个元素求一次全局Top-K。这里局部Top-K之所以可以用堆就是因为它能把每台机器的数据压缩到K个“最有希望的候选者”大大减少网络传输量。4. 工程中的堆优先级队列、中位数与图算法堆结构在工程里很少以“堆排序”的名字出现而是以“优先队列Priority Queue”这个更抽象的身份立足。很多开发者天天在用但未必意识到底层就是堆。这一节我结合自己实际接触过的场景挑几个最典型的讲讲。4.1 线程池的阻塞队列为什么经常用优先队列线程池的任务队列通常有两种选择普通 FIFO 队列和优先队列。FIFO 适合任务之间没有优先级差异的场景但真实系统里总有“紧急任务要插队”的需求。比如一个外卖派单系统普通订单可以排队但VIP用户投诉订单必须优先处理。如果直接用数组实现插队平均复杂度 O(n)如果用一个基于堆的优先队列插入和取出的复杂度都是 O(log n)。C 里对应std::priority_queueJava 里对应PriorityQueuePython 里是heapq。我第一次用优先队列做任务调度时犯过一个错直接用默认的std::priority_queueTask但Task自定义类型没有重载编译报错。解决办法是提供比较器注意C里的比较器写法容易把方向搞反——想取“优先级最高”的任务比较器写法跟你想的常相反。这个在后面常见问题里再展开。4.2 数据流中位数一边一个大根堆一边一个小根堆求一个不停增长的数据流的中位数也是堆结构的经典应用。思路是维护两个堆大根堆存放“较小的一半”元素堆顶是这一半的最大值小根堆存放“较大的一半”元素堆顶是这一半的最小值。只要保证两堆元素个数之差不超过1那么中位数要么是某个堆顶要么是两个堆顶的平均值。插入时先根据大小关系决定放进哪个堆然后通过调整维持两个堆的大小平衡。插入 O(log n)取中位数 O(1)。这题我面试时遇到过好几次代码不长但很考验对堆类型和大小平衡的理解。我第一次写脑子一热把新元素直接塞进大根堆导致两堆严重失衡中位数算错。后来养成了固定流程先塞进大根堆再把大根堆的堆顶移到小根堆最后如果大根堆比小根堆多出超过1个元素再做一次平衡。这样写看起来多几步但逻辑清晰不易错。4.3 Dijkstra 和 Prim 算法里的堆优化图算法里 Dijkstra 最短路、Prim 最小生成树核心瓶颈都是“每次从未确定集合里取距离最小的点”。如果每次都用线性扫描复杂度 O(V²)如果用普通数组维护距离堆优化可以把时间复杂度压到 O(E log V)。Dijkstra 的标准做法是用优先队列存 (距离, 节点) 对每次弹出距离最小的节点如果旧信息已经过期就跳过。这里的“过期”判断很多人一开始不太理解堆里可能同一个节点被更新过多次所以要从堆里弹出节点时发现它记录的距离已经大于当前已知最短距离就说明这一条是旧信息直接丢弃。堆在处理这类“动态取最小值”的问题里几乎是标准答案。理解了这一层你就会发现堆并不是排序算法的附庸它在调度、搜索、流式计算里无处不在。5. 常见问题、调试技巧与选型建议这一节把我在实际写代码和帮别人 review 时遇到的高频问题集中整理一下尤其是那些“看代码逻辑明明对但一跑就错”的坑。5.1 堆排序高频 Bug 清单先看代码怎么写会踩坑坑具体表现排查思路下滤时忘记判断孩子越界数组访问越界或排序结果为随机值确认left heapSize、right heapSize都判断0-based 和 1-based 混用建堆用(n-2)/2下滤用2*i1组合起来出错统一一套下标公式推荐0-based大根堆小根堆方向写反排出来的序是反的Top-K 结果刚好是“最差K个”拿 [3,1,2] 这种小数组手跑一遍排序循环里堆大小没缩小每次下滤都对全数组已排好的元素又被打乱确认heapSize在每轮交换后递减递归下滤栈溢出数据规模较大时崩溃改成迭代下滤调试堆排序我最常用的方法在siftDown开头加一行打印当前i和数组状态然后用一个长度为 58 的小数组跑一遍观察每一轮调整是否符合预期。堆的调试最怕“逻辑看着对”所以尽量使用小样本手工推导。5.2 Top-K 的边界与特殊输入Top-K 代码不难但边界条件非常容易在面试时被追问场景处理方法K 0直接返回空集合很多实现忽略这个导致除零或越界K n等价于全量排序或全量收集直接返回全部元素数组为空返回空集合大量重复元素堆解法天然支持重复值不会影响正确性无限数据流维护固定大小K的堆内存恒为 O(K)我面试时写 Top-K一定会在函数开头把k 0和k n两个分支写清楚。这两个分支不是代码难点但能体现你考虑问题是否全面是个加分项。5.3 堆排序 vs 快排 vs 归并到底什么时候用谁维度堆排序快速排序归并排序平均时间复杂度O(n log n)O(n log n)O(n log n)最坏时间复杂度O(n log n)O(n²)O(n log n)空间复杂度O(1)O(log n)递归栈O(n)稳定性不稳定不稳定稳定缓存局部性差好中等为什么 C 的std::sort不用堆排序因为堆排序虽然复杂度稳定但它的访问模式是“跳着访问”的数组下标从堆顶跳到堆尾缓存命中率很差。现代 CPU 上快排实际跑得比堆排序快不少。快排的退化问题可以通过三数取中、随机 pivot 等优化手段压制所以在通用库中快排更受欢迎。那堆排序到底什么时候用我个人经验是这几个场景需要手写且要求最坏情况下仍 O(n log n) 的算法题必须 O(1) 额外空间的排序需求作为实现优先队列的基础结构用在各种 Top-K、调度类场景。如果你只是在业务代码里给一个列表排序直接调用语言标准库就好没必要手写堆排序。堆排序价值的正确打开方式是搞懂那套“极值维护机制”然后把它迁移到 Top-K、优先级队列、中位数等场景里。最后再分享一个我自己的小习惯遇到任何要求“Top K”“最大/最小第K个”“每次取极值”的题目先不要急着排序。先问自己一句真的需要全部有序吗如果不需要堆往往就是比排序更优的答案。这套从堆结构到排序、再到选择问题的思路我用了很多年每次都能让我少写好几行代码也少踩好几个坑。