斐波那契堆由最小堆性质的树构成，通过循环双向链表连接根节点，支持O(1)摊还时间的插入与合并操作，提取最小值为O(log n)，适用于频繁合并场景。
斐波那契堆是一种高级优先队列结构，支持插入、查找最小值、合并、提取最小值和减小键值等操作，其中合并和插入的摊还时间复杂度为 O(1)，提取最小值为 O(log n)。相比二叉堆，它在需要频繁合并堆的场景中更高效。
基本原理与结构设计
斐波那契堆由一组满足最小堆性质的树组成，这些树以循环双向链表连接。每个节点包含以下信息：
- key：存储的数据值
- degree：子节点数量
- marked：标记节点是否丢失过一个子节点
- parent, child, left, right：用于构建树和根链表的指针
堆整体维护一个指向最小节点的指针，并通过级联剪枝和度数压缩优化性能。
C++ 实现关键部分
以下是简化但核心功能完整的实现框架：
立即学习“C++免费学习笔记（深入）”；
// 节点定义 struct FibNode { int key; int degree; bool marked; FibNode* parent; FibNode* child; FibNode* left; FibNode* right;explicit FibNode(int k) : key(k), degree(0), marked(false),
parent(nullptr), child(nullptr) {
left = right = this;
}};
// 斐波那契堆类（简化版） class FibonacciHeap { private: FibNode* min_node; int size;
// 将y链接为x的子节点
void link(FibNode* y, FibNode* x) {
// 从根链表移除y
remove_from_list(y);
y->parent = x;
if (!x->child) {
x->child = y;
y->left = y->right = y;
} else {
add_to_list(y, x->child);
}
x->degree++;
y->marked = false;
}
// 合并根链表到数组，进行合并操作
void consolidate() {
if (!min_node) return;
int max_degree = 0;
int sz = size + 1;
while ((1 << max_degree) <= sz) max_degree++;
std::vector A(max_degree, nullptr);
auto roots = get_root_list();
for (FibNode* w : roots) {
int d = w->degree;
while (A[d]) {
FibNode* u = A[d];
if (w->key > u->key) std::swap(w, u);
link(u, w);
A[d] = nullptr;
d++;
}
A[d] = w;
}
// 重建根链表并找新的最小值
min_node = nullptr;
for (FibNode* node : A) {
if (!node) continue;
if (!min_node) {
min_node = node;
min_node->left = min_node->right = node;
} else {
add_to_list(node, min_node);
if (node->key < min_node->key) {
min_node = node;
}
}
}
}
// 从双链表中移除节点
void remove_from_list(FibNode* node) {
node->left->right = node->right;
node->right->left = node->left;
}
// 将节点加入某链表（以anchor为头）
void add_to_list(FibNode* node, FibNode* anchor) {
node->left = anchor;
node->right = anchor->right;
anchor->right->left = node;
anchor->right = node;
}
// 获取当前所有根节点
std::vector get_root_list() {
std::vector roots;
if (!min_node) return roots;
FibNode* curr = min_node;
do {
roots.push_back(curr);
curr = curr->right;
} while (curr != min_node);
return roots;
} public: FibonacciHeap() : min_node(nullptr), size(0) {}
~FibonacciHeap() {
// 简化：实际应递归释放所有节点
while (min_node) extract_min();
}
bool empty() const { return min_node == nullptr; }
int top() const {
if (!min_node) throw std::runtime_error("Heap is empty");
return min_node->key;
}
void push(int key) {
FibNode* node = new FibNode(key);
if (!min_node) {
min_node = node;
} else {
add_to_list(node, min_node);
if (node->key < min_node->key) {
min_node = node;
}
}
size++;
}
int extract_min() {
if (!min_node) throw std::runtime_error("Heap is empty");
FibNode* z = min_node;
// 将z的所有子节点提升为根
if (z->child) {
auto children = get_children(z);
for (FibNode* child : children) {
add_to_list(child, min_node);
child->parent = nullptr;
}
}
remove_from_list(z);
int res = z->key;
if (z == z->right) {
min_node = nullptr;
} else {
min_node = z->right;
consolidate();
}
delete z;
size--;
return res;
}
// 获取某个节点的所有子节点
std::vector get_children(FibNode* node) {
std::vector result;
if (!node->child) return result;
FibNode* curr = node->child;
do {
result.push_back(curr);
curr = curr->right;
} while (curr != node->child);
return result;
}
// 合并另一个堆（O(1) 摊还时间）
void merge(FibonacciHeap& other) {
if (other.min_node == nullptr) return;
if (min_node == nullptr) {
*this = std::move(other);
return;
}
// 拼接两个根链表
FibNode* this_left = min_node->left;
FibNode* other_right = other.min_node->right;
min_node->left->right = other.min_node;
other.min_node->left->right = min_node;
FibNode* tmp = min_node->left;
min_node->left = other.min_node->left;
other.min_node->left = tmp;
if (other.min_node->key < min_node->key) {
min_node = other.min_node;
}
size += other.size;
other.min_node = nullptr;
other.size = 0;
} };
使用示例与注意事项
下面是一个简单的测试用法：
int main() { FibonacciHeap heap1, heap2;heap1.push(5);
heap1.push(2);
heap1.push(8);
heap2.push(3);
heap2.push(7);
heap1.merge(heap2); // O(1)
while (!heap1.empty()) {
std::cout << heap1.extract_min() << " ";
}
// 输出: 2 3 5 7 8}
注意：上述实现省略了 decrease_key 和 delete 操作，它们依赖于标记机制和级联剪枝，在图算法如 Dijkstra 中非常关键。生产环境需增加内存管理、异常安全和模板泛型支持。
基本上就这些，理解其摊还分析和树合并策略是掌握的关键。
