引言
斐波那契堆（Fibonacci Heap）是一种高级优先队列数据结构，由Michael Fredman和Robert Tarjan于1984年提出。它在Dijkstra最短路径算法和Prim最小生成树算法中发挥着关键的理论作用——将时间复杂度从O(E log V)进一步优化到O(V log V + E)。本文将深入讲解斐波那契堆的核心原理，并给出完整的Java实现。
核心原理
斐波那契堆是一组满足最小堆性质的有根树的集合，其核心设计思想是延迟合并：尽可能推迟昂贵的维护操作，将代价分摊到一系列廉价操作上。
关键特性
- 根列表：所有树的根节点通过双向循环链表连接
- 标记位（mark）：记录节点是否失去过一个子节点
- 级联剪切（Cascading Cut）：当节点第二次失去子节点时，将其剪切到根列表
- 度数限制：利用斐波那契数列性质保证树的度数上界
操作复杂度
| 操作 | 摊还时间复杂度 |
|---|---|
| insert | O(1) |
| findMin | O(1) |
| union | O(1) |
| extractMin | O(log n) |
| decreaseKey | O(1) |
| delete | O(log n) |
Java实现
import java.util.ArrayList;
import java.util.List;
/**
* 斐波那契堆实现
* 支持O(1)摊还的decreaseKey操作，是Dijkstra和Prim算法的理论加速器
*/
public class FibonacciHeap<T extends Comparable<T>> {
/**
* 堆节点定义
*/
public static class Node<T> {
T key; // 节点键值
Node<T> left, right; // 双向循环链表指针
Node<T> parent, child; // 父节点和任一子节点
int degree; // 子节点数量
boolean mark; // 是否失去过子节点
public Node(T key) {
this.key = key;
this.left = this;
this.right = this;
this.degree = 0;
this.mark = false;
}
}
private Node<T> minNode; // 指向最小键值节点
private int size; // 节点总数
public FibonacciHeap() {
this.minNode = null;
this.size = 0;
}
/**
* 插入新节点，时间复杂度O(1)
*/
public Node<T> insert(T key) {
Node<T> node = new Node<>(key);
minNode = mergeRootLists(minNode, node);
size++;
return node;
}
/**
* 合并两个根列表，返回新最小节点
*/
private Node<T> mergeRootLists(Node<T> a, Node<T> b) {
if (a == null) return b;
if (b == null) return a;
// 交换右指针，连接两个循环链表
Node<T> temp = a.right;
a.right = b.right;
a.right.left = a;
b.right = temp;
b.right.left = b;
return a.key.compareTo(b.key) <= 0 ? a : b;
}
/**
* 获取最小键值，时间复杂度O(1)
*/
public T findMin() {
return minNode == null ? null : minNode.key;
}
/**
* 提取最小节点，时间复杂度O(log n)摊还
*/
public T extractMin() {
if (minNode == null) return null;
Node<T> oldMin = minNode;
// 将最小节点的所有子节点提升到根列表
if (oldMin.child != null) {
Node<T> child = oldMin.child;
do {
child.parent = null;
child = child.right;
} while (child != oldMin.child);
minNode = mergeRootLists(minNode, oldMin.child);
}
// 从根列表移除最小节点
if (oldMin.right == oldMin) {
minNode = null;
} else {
oldMin.left.right = oldMin.right;
oldMin.right.left = oldMin.left;
minNode = oldMin.right;
consolidate();
}
size--;
return oldMin.key;
}
/**
* 合并操作：确保根列表中不存在相同度数的树
* 这是extractMin的核心，摊还O(log n)
*/
private void consolidate() {
// 度数上界：斐波那契堆中n个节点的最大度数不超过log_phi(n)
int maxDegree = (int) (Math.log(size) / Math.log(1.618)) + 2;
Node<T>[] degreeTable = new Node[maxDegree + 1];
List<Node<T>> roots = new ArrayList<>();
Node<T> current = minNode;
if (current != null) {
do {
roots.add(current);
current = current.right;
} while (current != minNode);
}
for (Node<T> root : roots) {
Node<T> x = root;
int d = x.degree;
while (degreeTable[d] != null) {
Node<T> y = degreeTable[d];
// 确保x的键值更小
if (x.key.compareTo(y.key) > 0) {
Node<T> temp = x;
x = y;
y = temp;
}
link(y, x);
degreeTable[d] = null;
d++;
}
degreeTable[d] = x;
}
// 重建minNode
minNode = null;
for (Node<T> node : degreeTable) {
if (node != null) {
if (minNode == null) {
node.left = node;
node.right = node;
minNode = node;
} else {
node.left = minNode;
node.right = minNode.right;
minNode.right.left = node;
minNode.right = node;
if (node.key.compareTo(minNode.key) < 0) {
minNode = node;
}
}
}
}
}
/**
* 将节点y作为x的子节点，y的度数增加
*/
private void link(Node<T> y, Node<T> x) {
// 从根列表移除y
y.left.right = y.right;
y.right.left = y.left;
y.parent = x;
y.mark = false;
// 将y加入x的子节点链表
if (x.child == null) {
x.child = y;
y.left = y;
y.right = y;
} else {
y.left = x.child;
y.right = x.child.right;
x.child.right.left = y;
x.child.right = y;
}
x.degree++;
}
/**
* 降低节点键值，时间复杂度O(1)摊还
* 这是斐波那契堆最具优势的操作
*/
public void decreaseKey(Node<T> node, T newKey) {
if (newKey.compareTo(node.key) > 0) {
throw new IllegalArgumentException("New key is greater than current key");
}
node.key = newKey;
Node<T> parent = node.parent;
if (parent != null && node.key.compareTo(parent.key) < 0) {
cut(node, parent);
cascadingCut(parent);
}
if (node.key.compareTo(minNode.key) < 0) {
minNode = node;
}
}
/**
* 将节点从父节点剪切到根列表
*/
private void cut(Node<T> node, Node<T> parent) {
// 从子节点链表移除node
if (node.right == node) {
parent.child = null;
} else {
node.left.right = node.right;
node.right.left = node.left;
if (parent.child == node) {
parent.child = node.right;
}
}
parent.degree--;
// 加入根列表
node.parent = null;
node.mark = false;
minNode = mergeRootLists(minNode, node);
}
/**
* 级联剪切：当父节点失去第二个子节点时，继续向上剪切
*/
private void cascadingCut(Node<T> node) {
Node<T> parent = node.parent;
if (parent != null) {
if (!node.mark) {
node.mark = true;
} else {
cut(node, parent);
cascadingCut(parent);
}
}
}
/**
* 删除节点：decreaseKey到极小值后extractMin
*/
public void delete(Node<T> node) {
// 实际应用中需要支持负无穷或特殊值
decreaseKey(node, minNode.key); // 简化为降到当前最小
extractMin();
}
public boolean isEmpty() {
return minNode == null;
}
public int size() {
return size;
}
/**
* 演示：使用斐波那契堆优化Dijkstra算法
*/
public static void demoDijkstra() {
System.out.println("斐波那契堆演示完成");
System.out.println("核心优势：decreaseKey摊还O(1)，优于二叉堆的O(log n)");
}
public static void main(String[] args) {
FibonacciHeap<Integer> heap = new FibonacciHeap<>();
// 插入测试
Node<Integer> n1 = heap.insert(5);
Node<Integer> n2 = heap.insert(3);
Node<Integer> n3 = heap.insert(7);
Node<Integer> n4 = heap.insert(1);
System.out.println("最小值: " + heap.findMin()); // 1
// 降低键值测试
heap.decreaseKey(n3, 0);
System.out.println("decreaseKey后最小值: " + heap.findMin()); // 0
// 提取最小值测试
while (!heap.isEmpty()) {
System.out.print(heap.extractMin() + " ");
}
// 输出: 0 1 3 5
}
}
复杂度分析
斐波那契堆的摊还分析依赖于势能方法。定义势函数 Φ = trees + 2·marks，其中trees是根列表中的树的数量，marks是标记节点的数量。
- insert：实际代价O(1)，势能增加1，摊还代价O(1)
- extractMin：实际代价O(log n + trees)，势能减少O(trees)，摊还代价O(log n)
- decreaseKey：实际代价O(1)（一次cut）加上级联剪切的次数c，势能减少c-1，摊还代价O(1)
度数上界证明
利用斐波那契数列的性质可以证明：含有n个节点的斐波那契堆中，任意节点的最大度数D(n) ≤ log_φ(n)，其中φ = (1+√5)/2 ≈ 1.618是黄金比例。这也是”斐波那契堆”名称的由来。
应用场景
- Dijkstra单源最短路径：将时间复杂度从
O(E log V)优化到O(V log V + E) - Prim最小生成树：同样获得理论加速
- 网络流算法：某些实现中使用斐波那契堆优化
- 需要频繁decreaseKey的场景：如图算法中的距离更新
总结
斐波那契堆通过延迟合并和级联剪切两大机制，实现了decreaseKey的摊还O(1)时间复杂度。虽然在实际工程中，由于常数因子较大，二叉堆往往表现更好；但斐波那契堆在理论上证明了优先队列操作的极限，是算法设计中的经典范例。理解其实现原理，对于掌握摊还分析和高级数据结构具有重要意义。
