什么是可合并堆？左偏堆、斜堆和二项堆解决了什么问题？
简化版
可合并堆重点解决的是「两个堆如何高效合并」。
普通二叉堆适合插入和删除堆顶，但合并两个堆通常需要把元素重新建堆，成本较高。左偏堆、斜堆、二项堆、斐波那契堆等结构，会把 merge 设计成核心操作。
它们常出现在算法竞赛、图算法理论和高级数据结构面试追问中，业务开发里不如普通堆常见。
详细版
普通二叉堆用数组表示完全二叉树，这让它缓存友好，但也让「合并」不方便。两个数组堆直接拼起来后，堆序未必成立，需要重新 heapify。
可合并堆一般采用指针结构，把合并两个堆设计成基础操作。
| 结构 | merge 特点 | 常见用途 |
|---|---|---|
| 左偏堆 | 利用零路径长保持右路径短 | 支持较快合并 |
| 斜堆 | 自调节，不显式维护距离 | 实现相对简单 |
| 二项堆 | 由多棵二项树组成 | 类似二进制进位合并 |
| 斐波那契堆 | 摊还复杂度优秀 | 理论分析常见 |
面试中不一定要求手写，但要知道它们解决的问题不是替代所有堆，而是优化 merge、decrease-key 等操作。
完整版教学
1. 普通二叉堆为什么不擅长合并
普通二叉堆最大的优势是数组紧凑存储。
但它的结构要求是完全二叉树，所以两个堆合并时不能简单把根连起来。最直接的做法是：
newArray = heapA + heapB
heapify(newArray)这个过程是 O(n + m)。
如果系统里经常要合并优先队列，比如合并多个事件集合、合并多个分支状态、合并多个集合的最小值，那么普通二叉堆就不够优雅。
2. 可合并堆的核心思想
可合并堆把 merge 当作核心操作。
一旦有了高效 merge：
- 插入一个元素可以看成「当前堆 merge 一个单节点堆」；
- 删除堆顶可以看成「merge 根节点的两个子堆」；
- 合并两个优先队列可以直接调用 merge。
可合并堆的设计哲学是：先把合并做好，其他操作自然变成合并的变体。
3. 左偏堆如何保持合并效率
左偏堆维护一个概念：零路径长，也就是到空节点的最短距离。
它要求左子树的零路径长不小于右子树，直觉上就是让右路径尽量短。
合并两个左偏堆时，通常沿着右路径递归合并：
merge(a, b):
if a is null: return b
if b is null: return a
if b.key < a.key: swap(a, b)
a.right = merge(a.right, b)
if npl(a.left) < npl(a.right): swap(a.left, a.right)
update npl(a)
return a因为右路径较短，所以合并效率较好。
4. 斜堆为什么说是自调节结构
斜堆和左偏堆很像，但它不显式维护零路径长。
它在每次 merge 时直接交换左右子树，依靠长期操作的摊还效果避免结构退化。
| 结构 | 是否维护额外信息 | 实现特点 |
|---|---|---|
| 左偏堆 | 维护零路径长 | 更有结构约束 |
| 斜堆 | 不维护距离 | 更简单，自调节 |
面试里可以把它类比成「类似 splay tree 的自调节思想」，不追求每一步绝对平衡，而追求整体摊还效率。
5. 二项堆为什么像二进制加法
二项堆由一组二项树组成，每个阶数最多一棵。
这和二进制数字很像：某一位要么有，要么没有。合并两个二项堆时，如果同阶树相遇，就把其中根较大的树挂到根较小的树下面，产生更高一阶的树。
B0 + B0 -> B1
B1 + B1 -> B2这种结构让二项堆的合并可以做到对数级。
6. 斐波那契堆为什么常出现在理论题
斐波那契堆的 decrease-key 摊还复杂度可以做到 O(1)，删除最小值是 O(log n)。
这让它在 Dijkstra、Prim 等算法理论复杂度分析里很漂亮。
但工程上它很少作为首选，因为：
- 指针结构复杂；
- 常数开销大；
- 缓存局部性差；
- 实现维护成本高；
- 标准库通常不提供。
所以面试回答要区分「理论复杂度」和「工程实践」。
7. 可合并堆和普通堆怎么选
可以按场景判断：
| 场景 | 更适合 |
|---|---|
| 只需要 push / pop | 普通二叉堆 |
| 需要频繁合并两个堆 | 可合并堆 |
| 追求标准库和稳定实现 | 普通优先队列 |
| 算法竞赛高级结构 | 左偏堆、斜堆、二项堆 |
| 理论复杂度分析 | 斐波那契堆 |
如果面试官问「为什么实际业务不用斐波那契堆」，重点回答常数、实现复杂度和缓存局部性。
8. 常见误区与追问
- 误区：可合并堆一定比二叉堆高级，所以更应该用。 它优化的是合并等特定操作，不是所有操作都更适合。
- 误区：普通二叉堆不能合并。 可以合并，只是通常要重新建堆，成本是线性级。
- 误区：斐波那契堆工程上一定最快。 它理论摊还复杂度好，但常数和实现复杂度很高。
- 追问：插入为什么可以看成 merge？ 因为插入一个元素等价于把当前堆和单节点堆合并。
- 追问：删除堆顶为什么也依赖 merge？ 删除根后，需要把根的子堆重新合成一个堆。