斐波那契堆由最小堆性质的树构成，通过循环双向链表连接根节点，支持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<FibNode*> 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<FibNode*> get_root_list() { std::vector<FibNode*> 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<FibNode*> get_children(FibNode* node) { std::vector<FibNode*> 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 中非常关键。生产环境需增加内存管理、异常安全和模板泛型支持。
基本上就这些，理解其摊还分析和树合并策略是掌握的关键。