第7章：堆与优先队列
元数据卡
- 难度: （需要的：递归思维 + 数组索引感）
- 前置: 第2章（数组）、第4章（递归与树的基本概念）
- 关键词: 二叉堆、上滤、下滤、Floyd建堆、堆排序、TopK、d-堆
- 实操环境: Python 3.10+，无外部依赖
你在哪
你不需要一次性处理所有事情——但要能最快地拿到最紧急的那件。森林里有一种神奇的石头堆，它总是把最重（或最轻）的石头放在最上面。
上一章你学会了哈希表——O(1)查任意元素。但生活中还有一个更刁钻的需求：我不关心谁最大，只想知道谁最有可能排第一。 这两种需求看似相近，背后的数据结构思维模式却天差地别。哈希表追求的是"平等"，任何元素来查都是常数时间；而堆追求的是"特权"——我只在乎那个站在最顶端的家伙，其他人排队等着就行。
想想这些森林里的场景：
- 林间医站分诊：受伤的冒险者多，但每次只处理伤势最重的。医者不会按名字排序，也不需要哈希——她只需要最快找到那个最需要抢救的人
- 森林精灵调度：几百个营地的物资同时需要运送，每次选优先级最高的那份先送。如果每次都要排序所有请求，森林早就乱套了
- 林间石碑名次：冒险者排行榜上每秒几千次积分更新，你只关心前 10 名是谁。全量排序？太奢侈了
- 兽道信使路由：林中信使每秒要处理百万级消息，每个消息有紧急标记。信使必须瞬间决定下一个递送谁
排序数组可不可以？每次插入 O(n)，慢了；每次取最值倒是快到 O(1)。但如果你插入比查询多，这就是灾难。
平衡二叉树（AVL / 红黑树）？O(log n) 可以，但实现动辄上千行，每个节点需要存父子指针、平衡因子、颜色标记……太重了。而且它的能力远远超过你的需求——你只是想要最值，它却能给你所有元素的全序关系。大炮打蚊子。
哈希表？堆上的"父子关系"它完全不理解，哈希的散列分布和大小比较是两条不同的路，走不到一块去。
于是堆出现了——一种更"偏科"的数据结构。它不做哈希的随机访问，不做 BST 的全序遍历，只做一件事：让我快速拿到最值。不求全知全能，只在你关心最值的时候快到飞起。这其实是计算机科学里一个重要的设计原则：限定能力换取效率。就像你应该用哈希表查元素、用数组做索引访问、用链表做中间插入——每种结构都有它的画风，堆的画风就是"我要最值"。
你的任务
本章分层
- 必读：堆的性质（完全二叉树 + 父节点 ≤ 子节点）；push（上滤）和 pop（下滤）的核心操作；优先队列的使用场景（Top K、合并有序序列）
- 选读：Floyd 建堆（O(n) 建堆）的原理；d-堆的概念（多叉堆）
- 深水区：Floyd 建堆的复杂度证明（级数求和）；数据流中位数（两个堆）——知道这是一个经典模式即可；堆排序的实现
本章不会要求你掌握
- Floyd 建堆 O(n) 的严格数学证明（能理解直觉即可：底层节点多但不动，顶层节点少但动得多）
- d-堆的详细分析
- 斐波那契堆
今天你需要完成三件事：
- 理解堆的性质：完全二叉树 + 父≤子的约束
- 模拟优先队列：实现 push（上滤）和 pop（下滤），理解每次取出的都是最值
- 用堆解决真实问题：Top K 问题——体会"用最小堆求最大 K 个"的反直觉设计
遭遇战 → 获得技能
第一战：营地的紧急事务
驿站长老让你维护一个物资分发队列。新任务随时来，但你必须永远优先处理最紧急的那件。
先看 Python 标准库是怎么做的（千万别说你不知道 Python 已经有现成的了——生产环境直接用，但面试你最好懂原理）：
# Python: heapq 是 min-heap
import heapq
tasks = []
heapq.heappush(tasks, (3, "写周报"))
heapq.heappush(tasks, (1, "修P0故障"))
heapq.heappush(tasks, (5, "重构代码"))
# 预期输出
while tasks:
print(heapq.heappop(tasks))
# (1, '修P0故障')
# (3, '写周报')
# (5, '重构代码')看到了吗？优先级 1 的总是先出来，不管我们按什么顺序插入的。heappush / heappop 各 O(log n)——不是 O(1) 但比 O(n) 快得多，而且足够满足绝大多数场景。这个"不是最快但够用"的特性，正是堆在工程中流行的原因。
第二战：谁才是"半有序"
堆是个完全二叉树——除了最后一层，上面全满；最后一层靠左填充。这个形状保证了数组表示是最紧凑的——没有空洞，没有指针开销。
存在数组里，索引 i 的：
- 左子 = 2i + 1
- 右子 = 2i + 2
- 父节点 = (i - 1) // 2
# 数组到树的映射
# 索引: 0 1 2 3 4 5 6
arr = [1, 3, 2, 7, 6, 4, 5]
# 树形（min-heap，父 < 子）：
# 1
# / \
# 3 2
# / \ / \
# 7 6 4 5小根堆性质：任意父节点 ≤ 其子节点。这不是二叉搜索树——你只知道根最小，其他节点之间没有任何全序关系。兄弟节点谁大谁小？不保证。3 和 2 之间你只知道 2 ≤ 4 和 2 ≤ 5，但 2 和 3 谁大谁小？堆没有义务告诉你。
"半有序"这个词精准描述了堆的本质：只有一半的信息（父子关系），另一半的信息（兄弟关系）被丢弃了。这种信息的有损压缩，正是堆能以 O(log n) 完成插入和取最值的代价。
第三战：上滤——新到的物资要学会"往上走"
插入一个新元素（假设 0），先扔到数组末尾，然后不断交换上去。这个过程叫"上滤"或"percolate up"。
想象一下，你刚在物资站领到一份火种，被暂时放在仓库最底层的角落里。但火种的优先级很高，于是你不断和上面的物资比——比不过就继续待在下面，比得过就和对方换位置。直到你上面的物资优先级都比你高，你才停下。
def heap_push(heap, val):
heap.append(val)
i = len(heap) - 1
# percolate up: 和父节点比，小就换
while i > 0:
parent = (i - 1) // 2
if heap[parent] <= heap[i]:
break
heap[parent], heap[i] = heap[i], heap[parent]
i = parent# 演示上滤
heap = [1, 3, 2, 7, 6, 4, 5]
heap_push(heap, 0)
print(heap)
# 输出: [0, 1, 2, 7, 3, 4, 5, 6]
# 小 0 一路攀到顶！传入的 0 比 5 小 → 换到 5 的位置。0 比 2 小 → 继续往上。0 比 1 小 → 到根。过程就像气泡向上冒——上滤的名字由此而来。
时间复杂度 O(log n)：树高就是 log₂n，每次上滤最多走一条从叶子到根的路径。
第四战：下滤——根被拔走后要"空降兵"
pop 最小值（根）后，堆就碎了。怎么办？把最后一个元素移到根，然后不断下沉：
def heap_pop(heap):
if not heap:
return None
if len(heap) == 1:
return heap.pop()
min_val = heap[0]
heap[0] = heap.pop() # 末尾顶上
i = 0
n = len(heap)
while True:
smallest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and heap[left] < heap[smallest]:
smallest = left
if right < n and heap[right] < heap[smallest]:
smallest = right
if smallest == i:
break
heap[i], heap[smallest] = heap[smallest], heap[i]
i = smallest
return min_valheap = [0, 1, 2, 7, 3, 4, 5, 6]
val = heap_pop(heap)
print(f"pop {val}, heap now: {heap}")
# pop 0, heap now: [1, 3, 2, 7, 6, 4, 5]下滤和上滤是镜像操作：上滤只和父节点比；下滤要在两个孩子中选更小的。选孩子的过程需要两次比较（左 vs 根，右 vs 胜者），这是堆操作中常数因子的主要来源。
为什么不把末尾元素上滤而用下滤？ 因为末尾元素通常很大（相对于堆的其它元素），把它放在根位置后，它还是应该沉到下面去。上滤是给小元素用的，下滤是给大元素用的。直觉：根被拔走后，顶上来的"替身"大概率比它的孩子大，所以要下沉。
进阶：Floyd 建堆——"底层先稳，再逐层向上"
本节为进阶内容。 主线先掌握 push/pop 和优先队列场景即可。Floyd 建堆是堆的高效初始化方法，推荐在掌握基础操作后再回来看。
给你一个无序数组 [3, 1, 6, 5, 2, 4]，怎么让它符合堆的性质？
错误做法：一个一个 push。push 一次 O(log n)，n 次就是 O(n log n)。虽然写起来最简单，但效率不是最优。
Floyd 的做法：从最后一个非叶节点（n//2 - 1）倒着往下滤。
为什么这样做？直觉是：叶子节点不需要处理（它们本身就是合法的堆，大小为 1）。从倒数第二层开始，每个节点向下滤时，它的子树已经是堆了——因为我们是从底向上处理的。
# Python: O(n) 建堆
def build_heap(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
_sift_down(arr, i, n)
def _sift_down(arr, i, n):
"""把 i 处的元素下滤到合适位置"""
while True:
smallest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] < arr[smallest]:
smallest = left
if right < n and arr[right] < arr[smallest]:
smallest = right
if smallest == i:
break
arr[i], arr[smallest] = arr[smallest], arr[i]
i = smallestarr = [3, 1, 6, 5, 2, 4]
build_heap(arr)
print(arr)
# 输出: [1, 2, 4, 5, 3, 6]
# 验证：检查每个父 ≤ 子
# 1
# / \
# 2 4
# / \ /
# 5 3 6 ✓手动模拟每次操作：
初始: [3, 1, 6, 5, 2, 4], n=6
n//2 - 1 = 2 → i=2 开始（元素 6）
i=2 (6): 左子=4→4<6? 是→交换 [3,1,4,5,2,6]
继续下滤 i=? 左子不存在→停止
i=1 (1): 左子=3→3<1? 否→左不变
右子=4→4<1? 否→右不变
停止，1 已经比两个子都小
i=0 (3): 左子=1→1<3? 是→交换 [1,3,4,5,2,6]
右子=2→2<3? 是→交换 [1,2,4,5,3,6]
left=2*0+1=1→3<1? 否→left 不变
left=5→5<3? 否→right 不变
停止
结果: [1, 2, 4, 5, 3, 6] ✓为什么是 O(n) 不是 O(n log n)？——关键直觉
大多数人刚学堆时都觉得建堆是 O(n log n)。这误会到面试翻车为止。这里是正确的直觉：
大多数节点在树的底层。倒数第二层有 n/4 个节点，每个下滤最多交换 1 次就到位；倒数第三层有 n/8 个节点，每个最多 2 次；以此类推。离根越近的节点越少，虽然它们交换次数多，但数量太少，影响不大。
总操作量 = 0×(n/2) + 1×(n/4) + 2×(n/8) + 3×(n/16) + ... = n × (1/4 + 2/8 + 3/16 + ...) = n × 1 = O(n)
来一个更直观的例子：一栋 20 层的大楼，Floyd 建堆从 19 层开始修——每层的人只需要往下走 0~1 层。如果从顶往下修（push 法），那 19 层的人要走 19 次才能到位。哪个快？显然是 Floyd。
d-堆——多生几个孩子会怎样？
本节为选读。 二叉堆（d=2）已经足够覆盖绝大多数场景。
二叉堆每个节点有 2 个孩子。如果改成 d 个孩子，树就变矮了（层数从 log₂n 变成 log_d n），下滤变快了（更少的层数）。但代价是每层比较的次数从 2 次变成 d 次。
# Python: d-堆实现片段
class DHeap:
def __init__(self, d=2):
self.heap = []
self.d = d # 每个节点最多 d 个孩子
def _parent(self, i):
return (i - 1) // self.d
def _child(self, i, k):
"""第 k 个孩子的索引（k 从 0 开始）"""
return self.d * i + k + 1
def push(self, val):
self.heap.append(val)
self._sift_up(len(self.heap) - 1)
def _sift_up(self, i):
while i > 0:
p = self._parent(i)
if self.heap[p] <= self.heap[i]:
break
self.heap[p], self.heap[i] = self.heap[i], self.heap[p]
i = p
def _sift_down(self, i):
n = len(self.heap)
while True:
smallest = i
for k in range(self.d):
c = self._child(i, k)
if c < n and self.heap[c] < self.heap[smallest]:
smallest = c
if smallest == i:
break
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
i = smallest| 分支因子 d | 树高 | 每层比较次数 | 总体下滤开销 |
|---|---|---|---|
| 2（二叉堆） | log₂n ≈ 20 | 2 | 40 |
| 3 | log₃n ≈ 13 | 3 | 39 |
| 4 | log₄n ≈ 10 | 4 | 40 |
| 8 | log₈n ≈ 7 | 8 | 56 |
你会发现 d=2 和 d=4 的下滤开销差不多，但 d=4 的数组访问更紧凑（locality 更好），cache miss 更少。某些场景下 4-堆比二叉堆还快。但在实战中，二叉堆仍然是默认选择——简单、通用、面试常考。
常见陷阱
堆排序——我建堆，你排序
堆排序 = 建堆（O(n)）+ 反复把根换到末尾 + 下滤剩余部分（n 次 × O(log n)）= O(n log n)。
关键看我们怎么用堆排序来做升序排列。升序 = 从小到大，所以我们需要最大堆——每次把最大的元素从根换到数组末尾，数组尾部就是排好的部分。
# Python 堆排序（原地、不稳定）
def heap_sort(arr):
n = len(arr)
# 建堆（最大堆）
for i in range(n // 2 - 1, -1, -1):
_sift_down(arr, i, n)
# 反复把根（当前最大值）放到末尾
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # 把最大值换到末尾（已排序区）
_sift_down(arr, 0, i) # 重新下滤剩余部分（长度逐渐缩短）
def _sift_down(arr, i, n):
"""
最大堆下滤：把 arr[i] 下沉到合适位置
注意这是最大堆版本！和前面的最小堆 _sift_down 不同
"""
while True:
largest = i
left, right = 2*i+1, 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 = largestarr = [4, 10, 3, 5, 1]
heap_sort(arr)
print(arr)
# 输出: [1, 3, 4, 5, 10]注意：上面用的是最大堆版本。升序排序必须用最大堆（把大数放末尾）。如果用最小堆，pop 出的最小元素放末尾→结果是降序排列。
堆排序的诡异之处：建堆 O(n)，排序 O(n log n)。前面建堆那么快，为什么排序慢下来了？因为每次 pop 根之后，末尾元素被放到根然后下滤——这个下滤是 O(log n) 的，做了 n 次。
对比一下各排序的常数因子（n = 1 亿）：
| 算法 | 时间复杂度 | 空间 | 稳定性 | 实战速度 |
|---|---|---|---|---|
| 快速排序 | O(n log n) | O(log n) 栈 | 最快 | |
| 归并排序 | O(n log n) | O(n) | 稳但吃内存 | |
| 堆排序 | O(n log n) | O(1) | 慢一点（cache不友好） | |
| 内省排序 | O(n log n) | O(log n) | 综合最强（C++ std::sort） |
堆排序虽然时间复杂度和快排一样，但常数因子大 2-3 倍——因为数组访问是跳跃式的（父节点和孩子节点的索引跨度 2 倍增长），cache miss 率远高于快排的顺序扫描。这也是为什么 C++ 的 std::sort 是内省排序（快排 + 堆排混合），而不是纯堆排序。
实战 1：Top K 问题——1 亿条日志，只要前 100
从海量数据中找出最大的 K 个元素。这是堆最经典的实战场景。
思路很反直觉：用最小堆维护大小为 K 的窗口。堆顶是当前最小的候选。新来的元素比堆顶大？把它加入堆，把最小的踢出去。最终堆里剩下的就是 Top K。
为什么用最小堆而不是最大堆？最大堆的堆顶是最大的，但你先 pop 掉的是最大的——你要找最大的 K 个，却先把最大的扔了，不合逻辑。用最小堆，每次淘汰的是当前最小的候选项。剩下的就是最大的。
# Python: Top K 最小堆解法
import heapq
import random
# 模拟 1 亿条日志（这里用 1 百万演示）
logs = [random.randint(0, 100000) for _ in range(1_000_000)]
K = 100
heap = []
for val in logs:
if len(heap) < K:
heapq.heappush(heap, val)
elif val > heap[0]: # 新元素比堆顶（当前最小候选项）大
heapq.heapreplace(heap, val) # pop + push 一步到位
print(sorted(heap, reverse=True)[:10]) # 前 10
# 输出: [99998, 99996, 99993, ...]时间复杂度：O(n log K)。当 K 远小于 n 时，近乎 O(n)。空间 O(K)。
对比一下其他方案：
- 全排序 O(n log n) —— 1 亿条日志全排？内存先爆炸。
- 快速选择 O(n) —— 找 Top 100 可以，但快速选择会破坏原数组，且不适合数据流（一次性全量输入）。堆则既是流式的又不破坏数据。
- 堆 —— 适合流式、大 K、不破坏原数据。实战之王。
实战 2：合并 K 个有序链表
你有 K 个有序列表，如何合并成一个有序列表？
暴力做法：把所有元素放到一个列表里，排序 O(N log N)。如果 N 很大但 K 很小，你这么干只是在浪费机会——列表已经有序了呀。
堆的做法：把每个列表的头部放入最小堆，每次 pop 出最小的元素，然后把该列表的下一个元素入堆。
# Python: 合并 K 个有序序列
import heapq
def merge_k_sorted(lists):
heap = []
result = []
# 每个列表的头入堆，同时记录来源和位置
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
while heap:
val, list_idx, pos = heapq.heappop(heap)
result.append(val)
if pos + 1 < len(lists[list_idx]):
heapq.heappush(heap, (lists[list_idx][pos+1], list_idx, pos+1))
return resultlists = [
[1, 4, 5],
[1, 3, 4],
[2, 6]
]
print(merge_k_sorted(lists))
# 输出: [1, 1, 2, 3, 4, 4, 5, 6]时间 O(N log K)，空间 O(K)（堆大小 + 输出）。当 K = 2 时退化到归并排序的 merge 阶段。当 K = N 时每个列表仅 1 个元素，堆大小为 N，复杂度退化为 O(N log N)。
多语言对比：TopK
| 语言 | 标准库堆 | 最大/最小 | 常用 API |
|---|---|---|---|
| Python | heapq | 最小堆（负数变最大堆） | heappush, heappop, heapify |
| Java | PriorityQueue<E> | 最小堆（可传 Comparator） | offer, poll, Comparator.reverseOrder() |
| C++ | std::priority_queue | 最大堆（greater<> 变最小堆） | push, pop, top |
// Java 版本：TopK 用最小堆
import java.util.PriorityQueue;
public class TopK {
public static void main(String[] args) {
int[] nums = {3, 2, 1, 5, 6, 4};
int k = 2;
// 最小堆：堆顶永远是当前最小
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int v : nums) {
heap.offer(v);
if (heap.size() > k) heap.poll();
}
System.out.println(heap); // [5, 6]
}
}// C++ 版本：TopK
#include <queue>
#include <vector>
std::vector<int> topK(const std::vector<int>& nums, int k) {
// 最大堆 = default（less<int>）
// 最小堆 = greater<int>
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
for (int v : nums) {
minHeap.push(v);
if (minHeap.size() > k) minHeap.pop();
}
std::vector<int> result;
while (!minHeap.empty()) {
result.push_back(minHeap.top());
minHeap.pop();
}
return result; // 升序结果
}注意 C++ 和 Java 语法的微妙差异：C++ 的 std::priority_queue 默认是 最大堆（less<int> 比较器，大的在堆顶），而 Java 的 PriorityQueue 默认是 最小堆。Python 的 heapq 默认也是最小堆。如果你在面试中写 C++ 并默认用了最大堆做 TopK，你的代码会出错——因为最大堆的堆顶是最大元素，你淘汰的是最大值。
通关挑战
动手之前别往下翻答案。
挑战 1：前 K 个高频元素
给一个数组，找出现频率前 K 高的元素。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1, 2] （出现频率前 2 高的）思路：先统计频率（哈希表），然后通过大小为 K 的最小堆，按频率排序。最终堆里留下的就是频率最高的 K 个。
def top_k_frequent(nums, k):
from collections import Counter
import heapq
freq = Counter(nums) # Python 神器：直接统计频率
# 最小堆，按频率排序（频率、元素）
heap = []
for num, cnt in freq.items():
heapq.heappush(heap, (cnt, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for _, num in heap]
print(top_k_frequent([1,1,1,2,2,3], 2))
# 输出: [2, 1] （频率分别是 2 和 3）进阶挑战：数据流中的中位数
不断有数字流入，每次都能 O(log n) 找到当前中位数。
思路：两个堆——最大堆存左半边（所有 ≤ 中位数的元素），最小堆存右半边（所有 ≥ 中位数的元素）。保持两个堆大小最多差 1。
import heapq
class MedianFinder:
def __init__(self):
self.left = [] # 最大堆（存负数用 Python 最小堆模拟）
self.right = [] # 最小堆
def add_num(self, num):
# 先决定放左边还是右边
if not self.left or num <= -self.left[0]:
heapq.heappush(self.left, -num)
else:
heapq.heappush(self.right, num)
# 平衡两个堆
if len(self.left) > len(self.right) + 1:
val = -heapq.heappop(self.left)
heapq.heappush(self.right, val)
elif len(self.right) > len(self.left):
val = heapq.heappop(self.right)
heapq.heappush(self.left, -val)
def find_median(self):
if len(self.left) > len(self.right):
return -self.left[0]
return (-self.left[0] + self.right[0]) / 2.0mf = MedianFinder()
for x in [1, 2, 3]:
mf.add_num(x)
print(mf.find_median())
# 1
# 1.5
# 2这个"两个堆"的模式非常经典。它不直接回答"中位数在哪"，而是通过维持左右平衡来间接定义中位数的位置。你可以在很多需要"维护有序性但只关心边界"的场景中复用这个思路。
验收标准
完成本章后，你应该能闭眼回答：
- 给定一个无序数组，写出 Floyd 建堆的过程（从 n//2-1 开始倒着下滤），并解释为什么是 O(n) 而不是 O(n log n)——级数求和
- heap_push 和 heap_pop 各自的时间复杂度，下滤和上滤各自什么时候用
- 为什么堆排序不是稳定排序？（相等元素在反复 pop 中可能错位）
- 什么时候用堆而不是快速选择？（数据流 / 不断有新数据进来 / 不想破坏数组）
- 为什么堆的 cache 性能比快速排序差？（数组访问跳跃，父子节点索引跨度 2 倍增长）
- 最大堆和最小堆的区别，以及什么场景该用哪个
- d-堆选 d=4 的利弊（更矮的树 vs 更多的子节点比较，cache locality 改善）
常见卡点
卡点 1：建堆复杂度那个 Σ 是啥？
你看到 O(n) 觉得不对——明明调用了 n/2 次下滤，每次下滤最多 log n 层，为什么不是 O(n log n)？
问题在于"最多 log n 层"——下滤的层数取决于节点在树中的位置，而不是树高。靠近底层的节点几乎不下滤，而大部分节点都在底层。如果你用一个浅显的公司类比就懂了：
让整个林间驿站知道一个通知。驿站长老逐个通知每个冒险者 = O(n log n)——每个人都要传话，路径很长。长老通知队长，队长通知组长，组长通知队员 = O(n)——信息是逐层传播的，每一层的人只需要告诉下一层，工作量 = 节点数之和 = 每层 O(n/层数) 最终累加 = O(n)。Floyd 建堆就是后者：叶子节点啥也不做，往上每一层的节点做的下滤操作次数正好等于它到叶子的距离。
卡点 2：最大堆 vs 最小堆
Python heapq 只有最小堆。要最大堆怎么办？
- 存负数：
heappush(heap, -val)，取出后再次取反。简单粗暴。 - 或者用 Tuple 自定义：
(priority, item)的 priority 可以取反。 - 注意：取反法对大数有溢出风险（Python 自动 bigint 所以没事，但 Java 中要小心
Integer.MAX_VALUE）。
卡点 3：堆排序不稳定
考虑 [5a, 5b, 3]（5a 和 5b 值相等，但用标签区分顺序）。建堆后，5a 可能被换到 5b 后面，最后输出 [3, 5b, 5a]。虽然值相等，但顺序变了。
稳不稳定在排序算法里是个重要概念。如果两个元素相等，稳定排序不会改变它们的相对顺序。为什么堆排序不稳定？因为在"下滤"过程中，父节点和子节点交换时，子节点被交换到父节点的位置，父节点下沉，相等元素的先后顺序可能被破坏。比起归并排序的"严格按序合并"，堆排序对相同值的情感非常淡漠。
卡点 4：堆 vs 二叉搜索树
- 堆：只保证根最值，兄弟间无关系
- BST：完全有序，可以查任意元素的前驱和后继
你要找第 2 大的？堆不给力——除了 pop 一次，没有更好的办法。BST 则可以直接找最值的前驱。
选哪个？查任意元素时用 BST（AVL/红黑树），只关心顶值时用堆。一句话：BST 叫你全排列，堆叫你头号玩家。
现在不需要理解
- 斐波那契堆：插入 O(1)，decrease-key O(1)（摊还）。用于 Dijkstra / Prim 的理论最优。但实现太复杂，常数因子太大。实战中二叉堆 + 优化（如 Pairing Heap）更实用。
- d-堆理论细节：每个节点有 d 个孩子。下滤变快（层数减少），上滤变慢（每层比更多次）。d = 2 就是二叉堆。d = 4 在 cache 友好性上有时更快（数组跨度小，cache miss 少）。
- 严格证明 Floyd 建堆 O(n)：设高度为 h 的满二叉树，第 k 层有 n/2^k 个节点，第 k 层的节点需要下滤 h-k 次（大约）。总操作 = Σ_{k=0}^{h} (n/2^k)(h-k) = n Σ_{j=0}^{h} j/2^j ≤ 2n = O(n)。
- 左偏堆 / 斜堆：可合并堆的另一种实现，merge 操作 O(log n)。斐波那契堆之外的选择。
- 堆的 O(log n) 复杂度究竟意味着什么：n = 10 亿时，log₂n ≈ 30。你的优先队列操作在 10 亿规模的数据上只需要大约 30 次比较。这就是对数之美。
旅人笔记
堆可能是我在实战中用得最多的"非平凡"数据结构。不是因为它复杂，而是因为现实世界大多数查询都是 Top K 式的：我不需要第 7 大的，不关心第 98 亿小的，我只想要前 10。
写这章时我在想——其实"堆"这个词起得真好。堆栈的堆，堆积的堆。一堆东西，你只想知道最上面是啥。像极了你办公桌上的文件堆——你永远只需要最紧急的那份。但另一个层面想，堆也代表了"粗糙的管理方式"：我不关心所有人的具体排名，我只关心最突出的那个。这很像一家初创公司——CEO 可以不知道每个人在做什么，但他必须知道谁是最重要的客户。
关于堆我还有一个小观察：用最小堆求最大 K 个是最反直觉但最优雅的设计之一。你脑子里想的是"我要最大的那些人"，但你的代码却在维护一个只包含"最小的候选者"的堆。这种思维的反转，就是"把不可能的问题转化成已知问题"的精髓。
记住三句话就够了：
- 上滤 = 新人插队向上爬（push）
- 下滤 = 空降顶上往下沉（pop / Floyd 建堆）
- Floyd = 从底到顶下滤，不是从顶到底插入——这就像盖楼先打地基，从底层开始，而不是先盖顶层再考虑下面的承重
哦对了，面试时如果有人问你"堆和优先队列的关系"——堆是实现优先队列的一种具体数据结构，不是等价。优先队列是抽象概念（一个队列，但出队时返回优先级最高的元素），堆是它的一个经典实现。优先队列也可以用其他方式实现（比如未排序链表，O(1) 入队 O(n) 出队，但很少人用）。
以及，一个很好用的 debugging 技巧：当你调试堆时，不用把整棵树画出来——用 heapq 的 heapify 功能建堆后，直接 for i in range(n//2): print(arr[i], arr[2*i+1], arr[2*i+2]) 检查父子关系。如果 i 的左右子都 ≥ arr[i]（最小堆）或 ≤ arr[i]（最大堆），堆性质就满足。
🔮 下一站预告
你已经学会如何快速拿到"最值"。但如果你想知道元素之间的全部关系——谁和谁相连、谁是通路、谁是孤岛——那你就需要图了。
下一章：图。DFS、BFS、拓扑排序、连通分量、二分图检测。你准备好了吗？