【数据结构与算法体系】斐波那契堆

一、引言：为什么我们需要斐波那契堆

1.1 二叉堆的局限

标准二叉堆（Binary Heap）支持以下操作的复杂度：

• insert：$O(\log n)$
• findMin：$O(1)$
• extractMin：$O(\log n)$
• decreaseKey：$O(\log n)$

对于 Dijkstra 最短路径算法，使用二叉堆的总时间为 $O((V+E) \log V) = O(E \log V)$。对于稀疏图（$E = O(V)$），这是 $O(V \log V)$——已经不错了。但我们能做得更好吗？

关键瓶颈：Dijkstra 算法中 decreaseKey 操作被调用了 $O(E)$ 次，如果能将 decreaseKey 的复杂度从 $O(\log n)$ 降到 $O(1)$，总复杂度就能降到 $O(E + V \log V)$！

斐波那契堆（Fibonacci Heap）正是为了实现这个目标而发明的。它由 Fredman 和 Tarjan 在 1984 年提出，以摊还分析为基础，实现了 decreaseKey 的 $O(1)$ 摊还时间。

1.2 斐波那契堆复杂度概览

┌──────────────────┬──────────────┬──────────────┐
│     操作          │   二叉堆      │  斐波那契堆   │
├──────────────────┼──────────────┼──────────────┤
│ findMin          │ O(1)        │ O(1)         │
│ insert           │ O(log n)    │ O(1)*        │
│ extractMin       │ O(log n)    │ O(log n)*    │
│ decreaseKey      │ O(log n)    │ O(1)*        │
│ delete           │ O(log n)    │ O(log n)*    │
│ merge (union)    │ O(n)        │ O(1)*        │
└──────────────────┴──────────────┴──────────────┘
* 均摊

---

二、斐波那契堆的结构

2.1 基本构成

斐波那契堆不是一棵树，而是一个森林（Forest）——具体地说，是一组满足最小堆性质的树的集合。

核心要素：

min(H) ──→ [3]↔[7]↔[11]↔[5]   ← 根链表（双向循环链表）
            │       │
           [8]     [12]
            │
           [9]

• 根链表（Root List）：所有树的根节点通过双向循环链表连接在一起
• **最小指针 min(H)**：指向根链表中键值最小的节点
• 每个节点存储：key（键值）、degree（子节点数目）、mark（标记位）、parent（父节点引用）、child（任意一个子节点引用）、left/right（循环链表的前驱后继）

2.2 节点的 Java 表示

class FibonacciHeap<K extends Comparable<K>, V> {
    
    static class Node<K, V> {
        K key;
        V value;
        Node<K, V> parent;
        Node<K, V> child;   // 指向任意一个子节点
        Node<K, V> left;     // 左兄弟
        Node<K, V> right;    // 右兄弟
        int degree;          // 子节点数量
        boolean mark;        // 是否曾失去过子节点
        
        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.left = this;
            this.right = this; // 初始时与自己构成循环
            this.degree = 0;
            this.mark = false;
        }
    }
    
    private Node<K, V> min;  // 最小节点
    private int size;        // 堆中节点总数
}

结构性质：

• 每个节点的子节点也通过双向循环链表连接（子链表）
• 根链表中各树的 size 和形状可以任意——没有二叉堆那样的结构性约束
• 只在 extractMin 时通过 Consolidate（合并） 过程将森林整理为”不同 degree 的树至多一棵”的状态

2.3 势能函数

摊还分析使用的势能函数：

$$\Phi(H) = t(H) + 2m(H)$$

其中：

• $t(H)$：根链表中树的数量
• $m(H)$：已标记（marked）节点的数量

这个势能函数的选择并非显而易见，它来自对 cut 操作（及其级联版本）的精细分析。简言之，每次 cut 增加 $t(H)$（新根）但可能减少 $m(H)$（被切断的标记节点取消标记）。势能的净变化使得 decreaseKey 的摊还成本保持在 $O(1)$。

---

三、核心操作实现

3.1 Insert — $O(1)$ 实际

public void insert(K key, V value) {
    Node<K, V> node = new Node<>(key, value);
    // 将新节点插入根链表
    if (min == null) {
        min = node;
    } else {
        insertIntoRootList(node);
        if (key.compareTo(min.key) < 0) {
            min = node;
        }
    }
    size++;
}

private void insertIntoRootList(Node<K, V> node) {
    // 插入到 min 的左侧
    node.left = min.left;
    node.right = min;
    min.left.right = node;
    min.left = node;
}

代价分析：$O(1)$ 实际时间。$\Delta\Phi = +1$（多一棵根树），但因为我们关心的是摊还界而非单次操作，这完全可接受。

3.2 Find-Min — $O(1)$

public V findMin() {
    if (min == null) throw new NoSuchElementException();
    return min.value;
}

只需返回 min 指向的节点的值。$O(1)$ 实际时间。

3.3 Union (Merge) — $O(1)$ 实际

public void union(FibonacciHeap<K, V> other) {
    if (other.min == null) return;
    if (min == null) {
        min = other.min;
        size = other.size;
        return;
    }
    // 连接两个根链表
    Node<K, V> a = min.right;
    Node<K, V> b = other.min.left;
    min.right = other.min;
    other.min.left = min;
    a.left = b;
    b.right = a;
    
    if (other.min.key.compareTo(min.key) < 0) {
        min = other.min;
    }
    size += other.size;
}

连接两个循环链表: 只需常数次指针操作。摊还分析：$\Delta\Phi = 0$（净增根树数不变），摊还 $O(1)$。

3.4 Extract-Min — $O(\log n)$ 摊还

这是最复杂的操作，分三步：

步骤 1：移除 min 节点，将其所有子节点提升为新的根（加入根链表）。

步骤 2：Consolidate（合并）：扫描根链表，将度（degree）相同的树合并，确保最终每棵树的度唯一。

步骤 3：扫描新的根链表，更新 min 指针。

public V extractMin() {
    Node<K, V> z = min;
    if (z == null) throw new NoSuchElementException();
    
    // 步骤1：将z的所有子节点提升为根
    if (z.child != null) {
        Node<K, V> child = z.child;
        do {
            Node<K, V> next = child.right;
            insertIntoRootList(child);
            child.parent = null;
            child = next;
        } while (child != z.child);
    }
    
    // 从根链表中移除z
    removeFromRootList(z);
    size--;
    
    if (z == z.right) {
        min = null; // 堆变为空
    } else {
        min = z.right;
        consolidate(); // 步骤2 + 3
    }
    return z.value;
}

private void consolidate() {
    // 辅助数组：degreeToTree[d] = 度为d的树的根
    int maxDegree = (int) Math.floor(Math.log(size) / Math.log(1.618)) + 1;
    @SuppressWarnings("unchecked")
    Node<K, V>[] degreeToTree = new Node[maxDegree + 1];
    
    // 收集所有当前根
    List<Node<K, V>> roots = new ArrayList<>();
    Node<K, V> curr = min;
    do {
        roots.add(curr);
        curr = curr.right;
    } while (curr != min);
    
    for (Node<K, V> x : roots) {
        int d = x.degree;
        while (degreeToTree[d] != null) {
            Node<K, V> y = degreeToTree[d]; // 另一个度为d的树
            if (x.key.compareTo(y.key) > 0) {
                // 交换，确保x是较小的根
                Node<K, V> tmp = x; x = y; y = tmp;
            }
            link(y, x); // 将y作为x的子节点
            degreeToTree[d] = null;
            d++;
        }
        degreeToTree[d] = x;
    }
    
    // 重建根链表
    min = null;
    for (Node<K, V> root : degreeToTree) {
        if (root == null) continue;
        if (min == null) {
            root.left = root.right = root;
            min = root;
        } else {
            insertIntoRootList(root);
            if (root.key.compareTo(min.key) < 0) {
                min = root;
            }
        }
    }
}

// 将child作为parent的子节点（child是另一棵树的根）
private void link(Node<K, V> child, Node<K, V> parent) {
    removeFromRootList(child); // child不再是根
    child.parent = parent;
    if (parent.child == null) {
        parent.child = child;
        child.left = child.right = child;
    } else {
        // 插入到parent的子链表中
        child.left = parent.child;
        child.right = parent.child.right;
        parent.child.right.left = child;
        parent.child.right = child;
    }
    parent.degree++;
    child.mark = false; // 新成为子节点，清除标记
}

复杂度和正确性分析：

consolidate 的摊还代价为 $O(\log n)$。关键观察：

• 在 consolidate 之前，根链表中最多有 $t(H_z) + \deg(z)$ 棵树（原来的根树 + z 的子节点）
• consolidate 过程中，每棵树的度不超过 $D_{\max} \approx \log_\phi n$（其中 $\phi = \frac{1+\sqrt{5}}{2}$ 是黄金比例——这与斐波那契数列紧密相关，也是”斐波那契堆”名称的由来）
• 扫描所有根树：$O(t(H_z) + \deg(z))$
• 每次 link：$O(1)$，至多 $O(t(H_z) + \deg(z))$ 次
• 总实际成本：$O(t(H_z) + \deg(z))$

摊还代价：$\hat{c} = O(t(H_z) + \deg(z)) + \Delta\Phi$。在 consolidate 后，根链表中至多 $D_{\max} + 1$ 棵树，因此势能从 $t(H_z) + 2m(H_z)$ 降至至多 $(D_{\max} + 1) + 2m(H_z)$。$\Delta\Phi \leq (D_{\max} + 1) - t(H_z)$。最终 $\hat{c} = O(D_{\max} + \deg(z)) = O(\log n)$。

3.5 Decrease-Key — $O(1)$ 摊还

这是斐波那契堆的招牌操作，也是它超越二叉堆的关键。

操作流程：

1. 减小节点 $x$ 的键值
2. 如果 $x$ 是根（无父节点）或新键值 $\geq$ 父节点键值 → 完成
3. 否则执行 Cut（切断）：将 $x$ 从父节点下切出，成为新根
4. 执行 Cascading Cut（级联切断）：如果父节点 $p$ 的 mark = true，递归切断 $p$

public void decreaseKey(Node<K, V> x, K newKey) {
    if (newKey.compareTo(x.key) > 0) {
        throw new IllegalArgumentException("新键值不能大于当前键值");
    }
    x.key = newKey;
    
    Node<K, V> p = x.parent;
    if (p != null && x.key.compareTo(p.key) < 0) {
        cut(x, p);
        cascadingCut(p);
    }
    
    if (x.key.compareTo(min.key) < 0) {
        min = x;
    }
}

private void cut(Node<K, V> x, Node<K, V> parent) {
    // 从parent的子链表中移除x
    if (x.right == x) {
        parent.child = null; // x是parent的最后一个子节点
    } else {
        parent.child = x.right;
        removeFromList(x);
    }
    parent.degree--;
    
    // x成为新根
    insertIntoRootList(x);
    x.parent = null;
    x.mark = false;
}

private void cascadingCut(Node<K, V> y) {
    Node<K, V> z = y.parent;
    if (z != null) {
        if (!y.mark) {
            y.mark = true; // 首次失去子节点：标记
        } else {
            cut(y, z);      // 再次失去子节点：切断
            cascadingCut(z); // 递归
        }
    }
}

摊还分析（核心）：

设 decrease-key 触发了 $c$ 次 cut（包括最初的一次 + $c-1$ 次级联）。

• 实际代价：$O(c)$
• 势能变化：
  • 每次 cut 产生一个新根：$t(H)$ 增加 $c$
  • 首次 cut 的节点：若之前被标记，失去标记 → $m$ 减少 1。之后被 cut 的 $c-1$ 个节点原本都是被标记的（否则不会级联），全部失去标记 → $m$ 减少 $c-1$。但最后一个被切断的节点的父节点（如果存在且未标记）变为标记 → $m$ 增加 1。
  • 净 $\Delta m \leq -c + 2$（最坏情况：父节点本未标记，现在标记了）
• **$\Delta\Phi$**：$\Delta t + 2\Delta m \leq c + 2(-c+2) = 4 - c$
• 摊还代价：$\hat{c} = O(c) + (4 - c) = O(1)$

这就是为什么 decreaseKey 在斐波那契堆上是 $O(1)$ 摊还——昂贵的操作（多次级联切断）被势能的释放所补偿！

3.6 Delete

删除操作 = decreaseKey 到 $-\infty$ + extractMin：

public void delete(Node<K, V> x) {
    // 将x的键值最小化，使其成为堆的最小元素
    // 在实际实现中通常存储一个比所有键都小的哨兵值
    decreaseKeyToMinusInfinity(x);
    extractMin();
}

摊还 $O(\log n)$。

---

四、斐波那契堆在 Dijkstra 和 Prim 中的应用

4.1 Dijkstra 算法优化

标准 Dijkstra（二叉堆）：
$$T_{\text{binary}} = O(V \log V + E \log V) = O(E \log V)$$

斐波那契堆 Dijkstra：

• $V$ 次 extractMin：$O(V \log V)$ 摊还
• $E$ 次 decreaseKey：$O(E \cdot 1) = O(E)$ 摊还
• 总计：$O(V \log V + E)$

对于稀疏图（$E = O(V)$）：

• 二叉堆：$O(V \log V)$
• 斐波那契堆：$O(V \log V)$ —— 同阶，常数更大

对于稠密图（$E = O(V^2)$）：

• 二叉堆：$O(V^2 \log V)$
• 斐波那契堆：$O(V^2 + V \log V) = O(V^2)$ —— 阶的改进！

代码版（伪代码集成斐波那契堆）：

// Dijkstra with Fibonacci Heap
int[] dijkstra(List<Edge>[] graph, int s) {
    int n = graph.length;
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[s] = 0;
    
    FibonacciHeap<Integer, Integer> heap = new FibonacciHeap<>();
    @SuppressWarnings("unchecked")
    FibonacciHeap<Integer, Integer>.Node[] nodes = 
        new FibonacciHeap.Node[n];
    
    for (int v = 0; v < n; v++) {
        nodes[v] = heap.insert(dist[v], v).getNode();
    }
    
    while (!heap.isEmpty()) {
        int v = heap.extractMin().getValue();
        for (Edge e : graph[v]) {
            if (dist[v] + e.w < dist[e.to]) {
                dist[e.to] = dist[v] + e.w;
                heap.decreaseKey(nodes[e.to], dist[e.to]);
                // 此行是O(1)摊还 —— 斐波那契堆的核心优势！
            }
        }
    }
    return dist;
}

4.2 Prim 算法优化

与 Dijkstra 结构完全一致：$V$ 次 extractMin，$E$ 次 decreaseKey。同样从 $O(E \log V)$ 优化到 $O(V \log V + E)$。

---

五、斐波那契堆名称的由来

为什么叫”斐波那契”堆？

斐波那契堆中任意节点的度 $d$ 对应的子树大小有一个下界：

$$\text{size}(x) \geq F_{d+2} \geq \phi^d$$

其中 $F_k$ 是第 $k$ 个斐波那契数（$F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, \ldots$），$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$ 是黄金比例。

证明概要（对 $d$ 归纳）：

考虑节点 $x$ 的 $d$ 个子节点 $y_1, y_2, \ldots, y_d$（按它们被链接到 $x$ 的顺序）。当第 $i$ 个子节点 $y_i$ 被链接到 $x$ 时，$x$ 至少有 $i-1$ 个子节点，因此当时 $y_i$ 至少有 $i-1$ 个子节点（因为 link 只合并度相同的树）。之后 $y_i$ 最多失去了 1 个子节点（因为首次失去时仅被标记，第二次失去时才被切断）。因此现在 $y_i$ 至少有 $i-2$ 个子节点。

递推得 $\text{size}(y_i) \geq F_{i} = F_{(i-2)+2}$，配合归纳假设可得 $\text{size}(x) \geq 1 + \sum_{i=2}^{d} F_i = F_{d+2}$。

由于 $\text{size}(x) \leq n$，我们有 $F_{d+2} \leq n$，因此 $d = O(\log_\phi n) = O(\log n)$。

这就是为什么 consolidate 中最大度不超过 $O(\log n)$——它直接来源于斐波那契数列的增长速度。

---

六、为什么斐波那契堆在理论上最优但实践中不被广泛使用？

这是每个学习斐波那契堆的人都应该问的问题。原因有几层：

1. 常数因子大：$O(1)$ 摊还的 decreaseKey 的实际常数（由于势能追踪、循环链表维护、标记/切断逻辑）远大于二叉堆中的 siftUp 操作。对于小到中等规模的数据，二叉堆实际上更快。

2. 内存开销：每个节点需要 4 个指针（parent、child、left、right）+ degree + mark。二叉堆只需要一个数组。

3. 缓存不友好：斐波那契堆的节点散布在堆内存中（链表结构），而二叉堆的数组存储在连续内存区域——对 CPU 缓存极度友好。

4. 复杂性：实现 decreaseKey 和 extractMin 的正确版本非常容易出错。

5. 实际图通常不够大：要使 $O(V \log V + E)$ 明显优于 $O(E \log V)$，需要 $E$ 足够大。许多真实图要么太稀疏（$E \approx V$，两者都是 $O(V \log V)$），要么使用更简单的优化（如 Pairing Heap、Radix Heap 在整数权重上更快）。

实践中的折中：java.util.PriorityQueue 使用二叉堆。在竞技编程中，绝大多数人使用二叉堆或 std::priority_queue。在真正需要最优理论复杂度的场景（如巨型网络流的某些专用求解器），斐波那契堆或其变体才会被考虑。

---

七、与其他堆的全面对比

┌──────────────┬──────────┬──────────┬──────────┬──────────┐
│     操作      │ 二叉堆   │ 二项堆   │ 斐波那契堆│ Pairing  │
│              │          │          │          │   Heap   │
├──────────────┼──────────┼──────────┼──────────┼──────────┤
│ findMin      │ O(1)     │ O(1)*    │ O(1)     │ O(1)     │
│ insert       │ O(log n) │ O(log n)*│ O(1)*    │ O(1)*    │
│ extractMin   │ O(log n) │ O(log n) │ O(log n)*│ O(log n)*│
│ decreaseKey  │ O(log n) │ O(log n) │ O(1)*    │ o(log n)*│
│ merge(union) │ O(n)     │ O(log n)*│ O(1)*    │ O(1)*    │
│ 实现复杂度    │ 简单     │ 中等     │ 难       │ 中等     │
│ 常数因子     │ 小       │ 中       │ 大       │ 中       │
└──────────────┴──────────┴──────────┴──────────┴──────────┘
* 表示均摊

---

八、面试常见追问

问题一：斐波那契堆的 decreaseKey 在什么具体场景下能体现优势？

回答：在图的规模极大且 decreaseKey 调用次数远多于 extractMin 的场景。例如 $V = 10^6$、$E = 10^9$（超大规模社交图上的 Dijkstra），$E$ 次 $O(1)$ 的 decreaseKey vs $E$ 次 $O(\log V)$ 的二叉堆 decreaseKey 有本质区别。但在经典面试题规模（$V \approx 10^5$）中，二叉堆完全够用。

问题二：为什么 mark 字段是必要的？没有它会发生什么？

回答：mark 机制（级联切断）防止了树变得”太瘦”——保证了任何度为 $d$ 的节点的子树至少有斐波那契级的大小。如果没有 mark，一个节点可能失去很多子节点却不被切断，导致树的度/大小比例恶化，consolidate 中的最大度不再受 $O(\log n)$ 约束，整个堆的复杂度保证崩溃。

问题三：如何确保 extractMin 后根链表中不会有太多树？

回答：consolidate 过程的核心作用就是去重。它利用 degreeToTree 数组，确保合并后任何 degree 至多出现一棵树。合并后根链表的树数量 ≤ $D_{\max} + 1 = O(\log n)$，从而为后续 extractMin 提供了复杂度保证。

问题四：decreaseKey 后为什么需要检查是否小于 min？

回答：decreaseKey 减小了某个节点的键值，如果该值小于当前最小值，新节点成为最小节点。更新 min 指针是 $O(1)$ 的。

问题五：如果只做 insert 和 extractMin，斐波那契堆会比二叉堆好吗？

回答：不会。如果不需要 decreaseKey 或 union，二叉堆在几乎所有指标上都优于斐波那契堆（更小的常数、更少的内存、更好的缓存）。斐波那契堆的优势完全体现在 $O(1)$ 的 decreaseKey 和 $O(1)$ 的 union 上。

---

九、总结

斐波那契堆代表了”摊还分析指导数据结构设计”的巅峰成就：

• 创新：用”懒惰合并”的策略（insert 只丢入根链表不做清理，extractMin 时才统一处理）将 decreaseKey 降到 $O(1)$ 摊还
• 代价：实现复杂性显著增加，常数因子大
• 理论意义：Dijkstra 和 Prim 的最优复杂度 $O(V \log V + E)$ 由此成为可能
• 实践地位：作为理论最优的优先队列，更多出现在算法教材和研究论文中，但在工程代码中常被二叉堆或 Pairing Heap 替代

理解斐波那契堆的关键收获不在于你是否会亲手实现它（大概率不会），而在于：(1) 摊还分析如何让”看似昂贵”的操作变得可接受；(2) “懒惰策略”（推迟清理工作）在数据结构设计中的威力。下一篇【数据结构与算法体系】不相交集数据结构 将展示另一种优雅的摊还分析应用。