1. 从实际问题切入：为什么还要翻堆排序的旧账
堆排序在算法面试里属于那种“看着简单、写起来总差一点”的类型。很多人背过它的时间复杂度是 O(n log n)、空间复杂度 O(1)，可真要在白板上写一个完全正确的堆排序，尤其是非递归版本的siftDown，翻车率非常高。更麻烦的是，堆排序单独出现的场景不多，更多时候它是以“TOPK问题”的面目出现在海量数据、排行榜、热点统计这类需求里。我见过不少开发者在处理“取前100个最大的数”时直接用全量排序，数据量一上来就卡死，原因就是没想起来堆这个结构。
堆的本质是“弱有序”：它不保证全局有序，只保证堆顶是最大（或最小）的那一个。这个特点很适合解决 TOP-K。求前 K 个最大元素时维护一个小顶堆，堆里始终保持当前看到的前 K 个候选；每来一个新元素，只和堆顶比较，比堆顶大就把堆顶替换掉，然后下沉调整。整个过程只需要遍历一遍数据，时间复杂度 O(n log K)，内存占用也只有 K 个元素。这个思路在大数据场景下的价值，远高于把全部数据排一遍再取前 K 个的暴力方案。
这篇文章我会从堆的结构本质开始，把堆排序的建堆、调整、排序三个阶段完整拆开，然后重点讲清楚 TOP-K 的堆解法为什么用小顶堆而不是大顶堆，代码怎么写，边界条件在哪。最后分享一些实际工程里踩过的坑，包括语言库优先级队列的默认行为、比较器方向搞反、K 的取值边界、以及时间复杂度上容易算错的地方。
不管你是准备面试还是做实际项目，建议你把这篇文章里的代码手动敲一遍。堆排序和 TOP-K 这东西，光看是不行的，自己动手写一遍、调一遍，才能真正变成你自己的东西。
2. 完全二叉树与堆的结构本质
2.1 数组怎么变成一棵树
堆排序的实现难点不在算法思想，而在“用数组表示一棵完全二叉树”。这个思维转换如果没建立起来，看代码会觉得每个parent、child下标关系都很抽象。一旦把数组想象成一棵铺满节点的树，所有操作都变得直观了。
完全二叉树的意思很简单：除了最后一层，其他每一层都是满的，最后一层的节点都靠左排列。堆恰好要求数据组织成完全二叉树，因为这种形态可以用数组紧凑存放，不需要指针，只需要通过下标计算找到父子关系。
假设根节点放在下标 0 的位置，那么对于任意下标i：
left = 2 * i + 1right = 2 * i + 2parent = (i - 1) / 2（向下取整，即整数除法）
这三个公式是堆所有操作的基石。建堆、调整、排序，每一步都在反复用这几个下标关系。我建议你在纸上画一棵 7 个节点的完全二叉树，给每个节点标上数组下标，然后用上述公式手动验证几次父子关系。比如下标 3 的节点，它的父节点是 (3-1)/2 = 1，左孩子是 2*3+1 = 7。画一遍之后，堆的代码再也不会觉得“绕”。
注意：如果根节点从下标 1 开始存放，那么左孩子是
2 * i、右孩子是2 * i + 1、父节点是i / 2。这两种写法在代码里很容易混。我的建议是统一使用从 0 开始的写法，因为它和几乎所有主流语言数组的下标习惯一致，减少出错概率。
2.2 大顶堆和小顶堆的区别
堆根据堆顶元素的大小关系分成两种：
- 大顶堆（最大堆）：堆顶是最大值，每个父节点的值大于等于其子节点。父节点是孩子的“天花板”。
- 小顶堆（最小堆）：堆顶是最小值，每个父节点的值小于等于其子节点。父节点是孩子的“地板”。
关键要理解：堆只保证父子之间的大小关系，不保证兄弟节点之间的大小关系。大顶堆里，根节点一定最大，但你无法确定左子树和右子树的值谁大谁小；你也不能说某一层的所有节点都比下一层的所有节点大——堆的有序性远比二叉搜索树来的松散。
用生活化的类比来说：大顶堆像一场比赛里层层选拔的冠军体系，每一级的“领队”一定比他的“队员”排名高，但两个不同小组的成员之间谁强谁弱，堆并不关心。这种弱有序性恰恰是堆高效的原因：维护堆的成本很低，不需要花费 O(n log n) 去维持全局排序，只要保持局部父子关系就够了。
2.3 堆的两个核心性质
堆的性质可以归纳为两点：结构性质和有序性质。
结构性质：堆必须是一棵完全二叉树。这意味着堆的形状完全由节点数量决定，可以用数组紧密存储，中间没有空洞。这个性质保证了操作的深度最多是 O(log n)——因为完全二叉树的高度天然就是 O(log n) 级别的。
有序性质：堆中任意节点的值必须满足父子之间的大小关系。大顶堆中，array[parent] >= array[child]对任意下标成立；小顶堆则相反。这个性质保证了堆顶元素一定是全局最大或全局最小，因为根节点没有任何祖先节点，它只需要满足与子节点的关系即可“晋级”到最顶端。
这两个性质合起来，让堆能够以非常高的效率完成三类操作：插入（追加元素后上浮）、取堆顶（直接读下标 0）、替换堆顶（新值放在下标 0 后下沉）。每类操作都是 O(log n)，这就是堆在 TOP-K 场景中大放异彩的根本原因。如果你理解了“插入是上浮、替换是下沉”这两个方向，堆排序和 TOP-K 的代码基本就能手写了。
3. 堆排序完整拆解：建堆、调整、排序
堆排序的流程标准化之后非常简单，三个阶段：无序数组建成堆 → 堆顶与末尾交换 → 缩小堆范围继续调整。但每个阶段都有不少容易写错的地方。我逐个拆开讲。
3.1 自底向上的建堆过程
给一个无序数组，怎么把它变成一个大顶堆？我最早看到别人代码里for (int i = n / 2 - 1; i >= 0; i--)觉得很奇怪，为什么从 n/2 - 1 开始往下遍历？这个细节值得彻底搞清楚。
完全二叉树的最后一层是叶子节点，叶子节点没有子节点，所以它们天然满足堆的性质。真正需要调整的，是从最后一个非叶子节点开始。最后一个非叶子节点是n/2 - 1（整除结果），这个下标可以这样推导：最后一个节点的下标是n-1，它的父节点是((n-1) - 1) / 2 = (n-2) / 2。在多数情况下，(n-2)/2的值等于n/2 - 1，你可以自己代入几个 n 验证。
从最后一个非叶子节点开始，从右往左、从下往上，对每个节点执行一次“下沉”（sift down）操作。所谓下沉，就是把当前节点和它的子节点比较，如果不满足父大于子的关系，就与较大的子节点交换；交换后还要继续向下比较，直到它落到一个满足堆性质的位置。
为什么必须自底向上而不是自顶向下？因为调整某个节点时，必须确保它的子树已经是一个合法的堆。从下往上处理，等到处理上层节点时，它下面的半堆都是合法的，这样只需要把“新来的”节点往正确位置移动即可。
我用一个具体数组来演示：[4, 10, 3, 5, 1]，n=5，最后一个非叶子节点下标是5/2-1 = 1，即值为 10 的节点。它的左孩子是下标 3 值为 5，右孩子是下标 4 值为 1，10 已经大于两个子节点，不需要调整。接下来处理下标 0 的节点，值为 4。它的左孩子下标 1 值为 10、右孩子下标 2 值为 3。较大的子节点是 10，10 大于 4，交换。交换后下标 1 处是 4，它还有子节点 5 和 1，较大的 5 大于 4，继续交换。最终数组变成[10, 5, 3, 4, 1]，大顶堆建立完成。
实操心得：建堆的时间复杂度是 O(n)，很多参考资料直接说是 O(n)。这个看起来有点反直觉，因为最朴素的直觉是所有节点都要下沉，每个下沉最多走 log n 层，应该是 O(n log n)。实际上，大部分节点的子树高度都很小，叶子节点完全不用下沉，倒数第二层的节点最多下沉 1 层，越靠近根部的节点下沉层数越深但数量越少。把每层节点数和最大下沉次数相乘再累加，最后是个常数级求和，收敛到 O(n)。这里不用死记硬背，理解“大部分节点都很矮、不需要层层下沉”就够了。
3.2 元素下沉（sift down）的实现细节
下沉是所有堆操作里最核心、最容易写错的部分。一个错误的实现可能让堆性质被破坏，导致排序结果完全错乱。
正确的下沉逻辑：
def sift_down(arr, n, i): # n 表示当前堆的有效范围，i 是需要下沉的节点 while True: 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: break arr[i], arr[largest] = arr[largest], arr[i] i = largest三个最常踩的坑：
- 忘记判断
left < n和right < n。超出有效范围的孩子并不存在，访问它们会产生非法下标或者读到堆外的数据。堆排序里n会随着排序进行而缩小，这个边界尤其关键。 - 先判断左孩子再判断右孩子，比较对象没有更新。正确写法是先用左孩子和当前节点比，选出较大的；再用右孩子和这个较大的值比。如果你把右孩子直接和
arr[i]比，你会漏掉“右孩子比当前节点大、但不比左孩子大”的那种情况，导致选错交换对象。 - 递归写法的隐藏性能问题。递归实现下沉在逻辑上没错，但每次递归都有函数调用开销。在数据量很大的情况下，递归会带来额外的栈压力和性能损耗。非递归版本用一个 while 循环解决问题，优先考虑。
3.3 排序阶段：堆顶与末尾交换
堆建好之后，大顶堆的堆顶就是整个数组的最大值。排序阶段的思路很直白：每次把堆顶和当前堆的最后一个元素交换，这样最大值就“安放”到了数组末尾。然后堆的有效范围减 1，此时新堆顶可能违反堆性质，再次执行下沉。
重复这个过程，直到堆的有效范围归零，数组就变成从小到大有序了。
def heap_sort(arr): n = len(arr) # 建堆 for i in range(n // 2 - 1, -1, -1): sift_down(arr, n, i) # 排序 for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0] sift_down(arr, i, 0) return arr注意这里的sift_down(arr, i, 0)第三参数是新的有效堆大小i，不再是数组总长度。因为i之后的元素已经是排好序的“禁区”，下沉过程绝对不能触碰它们。
实操心得：堆排序不是稳定排序。举个例子，两个相同的值，排序前后它们的相对顺序可能变化。如果业务需求要求排序稳定（例如先按分数排序，再按姓名排序且要保持分数相同的名字有序），就不能用堆排序。这时候用归并排序更合适。
3.4 复杂度分析：O(n log n) 与空间复杂度
堆排序的复杂度分三段看：
- 建堆：O(n)，前面说过原因是高度小的节点多。
- 排序阶段：每次交换后下沉最多 O(log n)，总共交换 n-1 次，所以是 O(n log n)。
- 整体：无论最好、最坏还是平均情况，堆排序都是 O(n log n)。这点和快排不同，快排最坏情况会退化到 O(n²)，而堆排序的最坏情况非常稳定。
空间复杂度是 O(1)，因为所有操作都在原数组上进行，只使用了常数个临时变量。这是堆排序最突出的优势之一：完全不需要额外的存储空间。
不过堆排序有个劣于快排的地方：局部性很差。数组访问模式是跳跃式的，比如访问下标 0、1、2、4 这些彼此不相邻的位置，CPU 缓存的利用率低。快速排序按顺序遍历数组分段，局部性好很多。所以实际工程中，即便堆排序的理论复杂度更稳定，很多排序库还是选择快排。堆排序更多被用在需要“流式处理”或者“外部排序”的场景里。
4. TOP-K 问题的堆解法
4.1 为什么海量数据求 TOP-K 绕不开堆
先明确一下 TOP-K 问题：在一组数据中找出最大（或最小）的 K 个元素。K 通常远小于数据总量 N。这类需求太常见了：热门商品榜单、高访问量页面、日志里出现次数最多的 IP、百万级学生中的尖子生名单……
最朴素的做法是全部排序取前 K 个，时间复杂度 O(n log n)。如果数据量特别大，大到无法一次性放入内存（比如几百 GB 的日志），全量排序根本不现实。退一步说，就算内存放得下，为了取 100 个最大元素把几千万个元素全部排序，也浪费得离谱。
堆解法完美绕开这两个问题：维护一个大小为 K 的小顶堆，遍历数据流一遍，时间复杂度 O(n log K)，内存占用 O(K)。因为 K 很小（比如 100），log K 近乎常数，整体效率非常高。而且它天然支持“流式处理”——数据不需要一次性全部加载，来一条处理一条，这对无法完全载入内存的大数据场景是决定性优势。
4.2 小顶堆求前 K 个最大元素的完整过程
很多人第一次接触会疑惑：要求前 K 个最大元素，为什么不维护一个大顶堆？
逻辑是这样的：如果你维护一个大顶堆，堆顶是当前堆里最大的元素。每来一个新元素，你拿它和堆顶比。如果新元素比堆顶大，说明新元素更大，但要怎么处理堆？要把新元素插入吗？那堆会变得越来越大，最终堆里存了所有比堆顶小的元素，这并没有筛出前 K 大。
反过来，如果维护一个大小为 K 的小顶堆，堆顶是堆里最小的元素。这个堆就像一个“守门员”：堆里始终存着当前遍历到为止的前 K 个最大候选。
- 如果来一个新元素比堆顶还小，说明在所有已见元素里它连前 K 大都不进，直接丢弃。
- 如果新元素大于堆顶，说明堆顶这个“前 K 最弱”已经被新元素淘汰了，把堆顶替换掉，然后下沉让小顶堆重新合法。
等整个数据流走完，堆里剩下的就是全局最大的 K 个元素（但不保证有序）。
用画外音来理解：小顶堆像一个精英包厢，容量固定 K 人。每来一个新人就看包厢里最弱的那个人是否被新人击败。如果是，把最弱的赶出去，新人顶替；如果不是，新人连门都进不了。任何时刻，包厢里的人都是截至目前见过的前 K 强。
4.3 完整代码与参数选择
TOP-K 的 Python 实现可以直接用标准库的优先队列，也可以自己手写小顶堆。先看用heapq的写法：
import heapq def top_k_largest(nums, k): if k <= 0: return [] # 先取前 k 个元素建堆 heap = nums[:k] heapq.heapify(heap) # 小顶堆 for num in nums[k:]: if num > heap[0]: heapq.heapreplace(heap, num) # 弹出堆顶，插入新元素 # 此时堆内元素即为最大 k 个 return heap注意这里用heapreplace而不是heappop+heappush。区别是：heapreplace先弹出堆顶再插入新元素，两步操作一次完成，效率更高；而heappop+heappush是两次独立操作，会多做一次堆调整。
如果要手写小顶堆，把前面的sift_down比较符号反过来（父节点比子节点小才合法）即可。我个人建议手动实现一次，体会一下比较方向翻转时largest -> smallest的细节变化，因为很多面试题是不允许使用标准库的。
重要提示：K 的取值必须大于 0 且小于等于数据总量。如果 K 等于数据总量，堆里存的就是全部数据，此时直接排序可能更快。如果 K 小于等于 0，结果是空列表。写代码时对 K 做个防御性判断，避免出现负数索引或逻辑错误。
4.4 与快速选择、全量排序的取舍
除了堆，TOP-K 还有两种常见解法：全量排序和快速选择（快速排序的变体，每次只往包含目标的一侧递归）。
全量排序最直观，适合 K 接近 N、或者数据量很小的情况。比如一个班级 50 人里取前 20 名，直接排序稳稳当当，没必要用堆。
快速选择在“只求前 K 个不要求这 K 个内部有序”的时候，平均时间复杂度可以做到 O(n)，比堆的 O(n log K) 更优。但快速选择有两个缺陷：一是最坏情况退化为 O(n²)，虽然可以通过随机化基准来缓解，但理论上仍有隐患；二是它必须一次性拿到全部数据，无法流式处理，也不适用于数据总量极大、无法全部载入内存的场景。
堆解法虽然平均性能不如快速选择，但它胜在稳定、内存占用小、支持流式处理。在海量数据、内存受限、数据以流的形式到达这几种情况下，堆是唯一可行的选择。实际工程选型建议：
| 场景 | 推荐方案 | 原因 |
|---|---|---|
| 数据量小（几千内），K 接近 N | 全量排序 | 实现简单，常数小 |
| 数据量中等，能全部载入内存，追求最快平均速度 | 快速选择 | 平均 O(n)，性能最强 |
| 数据量极大，无法一次性载入内存，或数据流式到达 | 堆 | 内存 O(K)，支持流式，稳定可靠 |
5. 实际工程中的坑与经验
5.1 语言库中优先级队列的默认行为
不同语言里“优先级队列”的默认方向完全不一样，我见过太多人栽在这里。
Python 的heapq默认是小顶堆，堆顶永远是最小值。这正好符合“求前 K 大”的需求，所以上面的代码直接用没问题。但如果你要取前 K 小，就得把数据取负再入堆，或者改用一个比较器的容器。
Java 的PriorityQueue默认也是小顶堆，这点和 Python 一致。但它支持传入Comparator，所以也可以很容易构造大顶堆：new PriorityQueue<>(Collections.reverseOrder())。
C++ 的priority_queue默认是大顶堆，堆顶是最大值。如果你维护priority_queue<int>来筛前 K 最大，逻辑就反了——你得改为priority_queue<int, vector<int>, greater<int>>才能构造小顶堆。
这个默认方向的差异是跨语言开发的高频翻车点。每次换语言写 TOP-K，先查一下语言库的默认方向，不要凭肌肉记忆写。
5.2 元素数量和 K 的边界问题
TOP-K 的边界条件非常容易写炸：
- K = 0：堆为空，任何比较都没有意义。
- K > N：数据总量不够 K 个，堆不可能装到 K 个元素。此时要么做防御性拿全部数据建堆，要么提前抛异常，绝不能直接按照 K 的容量去索引。
- K = N：堆里装了全部数据，时间复杂度退化为 O(n log n)，不如全量排序。
- 数据里存在大量重复值：前 K 大如果有并列，堆会保留其中任意的重复值，而不是把相同值的所有副本都纳入结果。如果业务上要求“并列排名都算”，比如第 100 名有 20 个人并列，那 TOP-K 只是一个忠实反映“截至当前已见的前 K 个候选”的算法，并不能保证把所有并列的人全部放进结果。
5.3 时间复杂度计算中的几个误区
不少人在实际项目中估算性能时会把堆的时间复杂度算错。
第一个误区：以为堆的每次操作都是 O(log n)。在 TOP-K 中，只要新元素不比堆顶大，连堆调整都不用做，直接丢弃。因此实际大量数据可能根本不会触发替换操作，平均处理成本往往远低于 O(log K)。
第二个误区：分不清 O(n log K) 和 O(n log n)。当 K 远小于 n 时，两者的差距非常大。比如 n = 1 亿，K = 100，前者大约是 1 亿乘以 7 次比较，后者大约是 1 亿乘以 27 次比较，差别接近 4 倍；而且前者内存只占几百个元素，后者需要存储整个数组。
第三个误区：把建堆当成 O(n log n)。如果你用逐个插入的方式建堆，每一次插入 O(log n)，总代价确实是 O(n log n)。但如果用heapify（自底向下调整）的方式，总代价是 O(n)。在 Python 里直接从nums[:k]建堆就是用heapify，这一步不要写成循环插入。
5.4 数据量级评估
实际项目里到底什么时候必须用堆？我的经验是直接做两组估算。
第一，看内存。假设每条数据是 8 字节的整数，10 亿条就是 8 GB。如果你的服务器可用内存只有 4 GB，全量排序已经不现实了。这时候如果 K = 100，堆解法只需要不到 1 KB 的内存，数据处理完全可以在线完成。
第二，看延迟。堆解法是单趟扫描，时间复杂度与 N 线性挂钩。如果 N 是 10 亿级，即使只取前 100 个，也要把这 10 亿条数据全部过一遍——这是所有必须“看完全部数据才能确定前 K”的算法都逃不掉的下限。如果数据是持续不断产生的流（比如点击日志），堆解法可以每来一条数据 O(log K) 地更新结果，做到“随时查询当前前 K”，这是排序和快速选择都做不到的。
实操心得：做海量 TOP-K 时，数据读取往往比堆调整更影响整体耗时。瓶颈常常在磁盘 IO 或者网络读取上。所以遇到性能问题，先优化数据的读取方式（比如分批读取、用更紧凑的数据结构、减少序列化开销），再考虑堆操作本身的微小优化。我曾经遇到一次很典型的情况：堆部分耗时只占总体不到 3%，90% 以上的时间都花在读日志文件和解析字符串上。调堆是缘木求鱼，换成按行缓冲读取之后性能立刻上来了。
5.5 自定义对象的堆比较方式
实际工程中，堆里存的往往不是数字，而是对象。比如日志统计中每个 IP 的访问次数、商品 ID 和它的销量。要让堆能比较这些对象，你需要告诉它按照什么字段来比。
Python 的heapq默认用对象的小于号比较，所以最简单的方式是让对象实现__lt__方法。另一个技巧是往堆里存元组，比如(次数, IP)，这样堆会按第一个元素比较，相同次数时再按第二个元素比较。
Java 中需要传入Comparator，比如Comparator.comparing(Item::getCount)。这里容易踩一个坑：Comparator.comparing默认升序，对 Java 的默认小顶堆来说，堆顶会变成次数最小的对象——这正好符合小顶堆求最大 K 的需求。但如果把PriorityQueue本身和小顶堆的关系搞混，几乎必然写出反的筛选逻辑。
实操心得：测试堆比较逻辑时，构造一个很小的用例，故意打乱顺序，打印每一步筛选过程中的堆内容。只用一两个元素的用例调试，通常 10 分钟就能发现比较方向问题，比猜来猜去快得多。
6. 堆排序与 TOP-K 的延伸应用
6.1 外部排序里的堆角色
当数据量巨大、磁盘上放都放不下的场景出现时，外部排序就会用到堆。典型的思路是：把大文件切成若干个小块，每块能够载入内存，对每块内部排序后写回磁盘，产生多个有序段；然后用一个大小为 M 的堆，从每个有序段各取一个当前最小值，堆顶就是全局最小，取出后从对应段补下一个值，反复进行直到全部输出。这个过程叫“多路归并”，堆在其中扮演了合并器的核心角色。
多路归并的复杂度分析很有意思：每个元素的堆调整成本从 O(1)（单路情况）变为 O(log M)，M 是路段数。当年我自己实现过一个模拟外部排序，最初的版本每取出一个元素就重新从 M 个段的头部找最小值，时间复杂度 O(N*M)，大约 100 万个元素处理了 40 多秒；改成维护一个 M 元小顶堆之后，同样的数据量在 1 秒内就完成了。差别非常直观。
6.2 定时器与任务调度
堆的应用不止排序和数据筛选。稍微跳出思维定式就能发现，任何“总是需要立刻知道最大或最小”的场景都和堆有关。
比如任务调度器里，系统维护一个按执行时间排序的最小堆，堆顶是最近要执行的任务。来一个新任务，插进堆里做一次上浮即可，调度器永远在 O(1) 时间内拿到下一个任务。这个结构比“每来一个任务就全量排序”高效得多。
网络通信里的滑动窗口限流也可以借助堆来维护时间戳集合，快速淘汰掉过期的请求记录。堆在这里不是主角，但作为基础数据结构，它随处可以当作“优先获取极值”的容器使用。
6.3 数据流中的 Top K 动态更新
回到真实业务：“实时榜单”几乎是每个内容平台都躲不掉的需求。每来一条新的播放记录，就要更新一次“当前播放量最高的前 10 个视频”。堆解法是这里最自然的方案：维护一个大小为 10 的小顶堆，每来一次播放就把对应视频的计数 +1，然后调整堆。如果视频数量本身很大，还可以先用哈希表维护每个视频的总播放次数，再在需要展示榜单时用堆从哈希表中筛选一次。这种“哈希表 + 堆”的组合非常常见。
7. 写代码时容易出现的低级错误
7.1 下标计算错误
堆操作所有下标都来自2*i+1、2*i+2、(i-1)/2这三个公式。写代码时最怕出现以下错误：
- 使用
(i-1)//2时忘记考虑负数。当 i = 0 时，(0-1)//2 在部分语言中可能得到 -1，非法访问数组。 - 左右孩子下标溢出。对于越界的
left和right，神智不清的开发可能直接访问 arr[left]，导致运行时错误。 - 循环时需要判断
child + 1 < n而不是child < n，否则第二个孩子会越界。
7.2 比较符号写反
大顶堆和小顶堆的实现只在比较符号上有区别：一个用>选最大的子节点，一个用<选最小的子节点。我建议不要靠死记硬背，而是通过手工模拟一遍——真的拿起笔在小数组上走一遍逻辑，你会发现比较符号一目了然。
7.3 建堆与排序顺序混淆
建堆是从n/2-1开始向左遍历；排序是从末尾开始向左交换堆顶，然后下沉。有些代码会把排序循环里的sift_down(arr, i, 0)写成sift_down(arr, n, 0)，导致已经排好的元素再次被拉进堆调整范围，破坏已排序部分。
这种错误经常发生在修改已有函数时，为了“省一次参数传递”，结果把整个算法搞坏。建议下沉函数始终显式接收有效堆大小n和当前节点下标i，参数传递多一行不碍事，但逻辑清晰度大幅提升。
8. 手写堆的两个经典实现方向
8.1 自顶向下插入法建堆
前文讲的heapify是自底向上建堆。还有一种自顶向下的方式：从一个空堆出发，每来一个新元素插到末尾，然后往上浮。每次上浮 O(log n)，总代价 O(n log n)。
这种方法比较直观，但效率比heapify低。它最大的价值在于插入操作本身：动态插入场景下，新元素从叶子一路浮到合适位置，代码实现很简单。
def heap_push(heap, val): heap.append(val) i = len(heap) - 1 while i > 0: parent = (i - 1) // 2 if heap[parent] <= heap[i]: break heap[parent], heap[i] = heap[i], heap[parent] i = parent8.2 自底向上替换法（TOP-K 专用）
TOP-K 里“替换堆顶”用heapreplace很顺手，但它有个前提：堆不是空的，而且新元素已经确定大于堆顶。如果你用“弹出堆顶再插入”的方式，弹出的值可能比新元素还大，堆元素数量将超过 K。这在堆的容量上是不允许的。
实操心得：实际实现 TOP-K 替换时，我见过一个隐蔽的 bug：先
heappop再heappush，代码逻辑看起来对，但堆容量短暂变为 K-1，此时如果另一个线程恰好读取了堆，就会得到错误的结果。不过单线程模式下不会触发这个 bug，只是多一次调整，性能略差。总之推荐直接使用heapreplace，不要先弹后插。
9. 从堆排序到 TOP-K 的思维跃迁
堆排序和 TOP-K 看似是两个独立问题，其实共享同一个核心思想：不必维护全局有序，只要维护局部有序即可。
堆排序利用“全局最大（或最小）总在堆顶”这个特性，通过一次次把堆顶放到末尾来逐步排序。TOP-K 利用“大小为 K 的堆总能代表前 K 个候选”这个特性，通过一遍扫描筛出答案。两者殊途同归，都建立在堆的 O(log n) 调整能力之上。
理解了这层关系，你还会发现堆的思想能迁移到很多场景：比如实时中位数（维护一个大顶堆和一个小顶堆，分别存上半部分和下半部分）、滑动窗口极值、哈夫曼编码里的最小堆选择等。堆不是孤立的知识点，它是一整套“极值优先”处理方式的基石。
我自己的体会是：学数据结构不能只背代码模板。你把堆的父子关系、上浮下沉、建堆顺序这些底层机制想清楚，再去看任何和堆相关的题，基本一眼就能拆出核心逻辑。遇到新问题也能很快想到“这个场景是不是一个极值维护问题”。数据结构知识最大的价值，是那种跳出具体实现、抽象出问题本质的能力。
如果你现在正准备面试，我的建议是：先把堆排序的手写代码练到肌肉记忆，再熟练 TOP-K 的两种写法（标准库版本和手写版本）。把两者融合贯通的关键在于多画图、多推演一遍每个步骤中堆内部发生了什么变化。画明白了，代码自然就会写了。
