二项堆 (Binomial Heap)、Fibonacci 堆详细解读
一、二项堆 (Binomial Heap)
二项堆（Binomial Heap） 是一种基于 二项树（Binomial Tree） 组成的堆结构，具有良好的时间复杂度特性。二项堆常用于实现优先队列，支持快速的合并操作（Union）。与二叉堆不同，二项堆是由多个二项树组成的集合，这些二项树满足最小堆或最大堆的性质。
1. 定义与特点
- 二项树：二项树 Bk 是一种递归定义的树结构：
- B0：单个节点。
- Bk：由两个 Bk−1 的二项树连接而成，一个树作为另一个树的左子树根的孩子。
- 二项堆：由一组不同阶数的二项树构成，满足最小堆性质（树的根节点是整个树的最小值）。
- 任何一个二项堆最多包含一棵同阶的二项树。
- 树的阶数：一个二项堆中的二项树，其阶数从 B0,B1,...,Bk 唯一且无重复。
2. 结构示意图
3. 核心操作
- 插入（Insert）：将元素作为一个单独的二项树（B0）插入，并通过 合并操作 调整堆结构。
- 合并（Union）：将两个二项堆合并成一个。若出现同阶的二项树，则将它们合并成更高阶的二项树。
- 查找最小值（Find Min）：遍历根链表，找到最小的根节点，时间复杂度为 O(logn)。
- 删除最小元素（Extract Min）：
- 找到最小根节点，删除该根节点。
- 将其子树分解为单独的二项树。
- 将这些树重新合并到二项堆中。
- 减少键值（Decrease Key）：将某节点的值减少，然后通过上浮操作调整位置。
- 删除节点（Delete Node）：通过减少键值到负无穷大，再进行删除最小元素操作。
4. 时间复杂度
| 操作 | 时间复杂度 |
|---|---|
| 插入 (Insert) | O(logn) |
| 合并 (Union) | O(logn) |
| 查找最小值 (Find Min) | O(logn) |
| 删除最小元素 (Extract Min) | O(logn) |
| 减少键值 (Decrease Key) | O(logn) |
| 删除节点 (Delete Node) | O(logn) |
二、Fibonacci 堆 (Fibonacci Heap)
Fibonacci 堆 是一种更高级的堆数据结构，与二项堆类似，但具有更好的渐进时间复杂度。它特别适合用于 Dijkstra 和 Prim 等最短路径算法，以及其他涉及优先队列的算法。
1. 定义与特点
- Fibonacci 堆由一组根列表组成，这些根节点形成一个最小堆序。
- Fibonacci 堆的每个节点都有一个指向其父节点和子节点的指针。
- 每个节点还保存其度数（子节点的数量）和标记位（用于减少键值操作的优化）。
- 松弛合并（Lazy Merging）：Fibonacci 堆在插入新元素和合并堆时延迟结构调整，因此其摊还复杂度较低。
2. 结构示意图
3. 核心操作
- 插入（Insert）：将新元素插入根列表中，时间复杂度 O(1)。
- 合并（Union）：将两个堆的根列表合并，时间复杂度 O(1)。
- 查找最小值（Find Min）：直接访问最小堆顶元素，时间复杂度 O(1)。
- 删除最小元素（Extract Min）：
- 移除最小根节点，并将其子节点加入到根列表。
- 重新调整堆结构，通过级联链接合并同度数的节点。
- 减少键值（Decrease Key）：
- 将节点值减小，如果破坏了最小堆性质，则切断该节点及其子树，将其加入根列表。
- 如果父节点已被标记，则继续向上递归。
- 删除节点（Delete Node）：将节点键值减小到负无穷大，然后执行删除最小元素操作。
4. 时间复杂度（摊还分析）
| 操作 | 最坏情况复杂度 | 摊还复杂度 |
|---|---|---|
| 插入 (Insert) | O(1) | O(1) |
| 合并 (Union) | O(1) | O(1) |
| 查找最小值 (Find Min) | O(1) | O(1) |
| 删除最小元素 (Extract Min) | O(logn) | O(logn) |
| 减少键值 (Decrease Key) | O(logn) | O(1) |
| 删除节点 (Delete Node) | O(logn) | O(logn) |
5. 应用场景
- Dijkstra 算法：用于单源最短路径，减少键值操作的优化可加速路径更新。
- Prim 算法：用于最小生成树算法。
- 其他优先队列应用：如事件调度系统、任务管理。
三、Fibonacci 堆 vs. 二项堆
| 特性 | 二项堆 | Fibonacci 堆 |
|---|---|---|
| 插入 (Insert) | O(logn) | O(1) 摊还时间 |
| 合并 (Union) | O(logn) | O(1)摊还时间 |
| 删除最小元素 (Extract Min) | O(logn) | O(logn) 摊还时间 |
| 减少键值 (Decrease Key) | O(logn) | O(1)摊还时间 |
| 应用场景 | 适合较少合并操作的场景 | 适合频繁合并、减少键值的场景 |
Fibonacci 堆在理论上的性能比二项堆更优，尤其是在 减少键值 和 合并操作 的情况下，但其实现较为复杂，因此在实际应用中，二项堆有时更具实用性。