斐波那契堆（Fibonacci Heap）原理与实现

斐波那契堆是一种用于优先队列操作的高效数据结构，特别擅长支持合并操作。它通过惰性管理和摊销分析，在插入、合并、减小键值等操作上达到O(1)时间复杂度，而删除最小元素操作的时间复杂度为O(log n)。

核心结构与设计思想
斐波那契堆由多个最小堆有序的树组成（不一定是二项树），采用"惰性合并"策略：新元素直接作为单节点树加入根链表，不立即整理结构，直到执行删除最小元素时才 Consolidate（合并）相同度数的树。

基本操作步骤详解

1. 插入操作

   • 创建一个单节点树（包含键值）
   • 将该树加入根链表
   • 若新节点键值小于当前最小指针，更新最小指针
   • 时间复杂度：实际O(1)，摊销O(1)

2. 合并两个斐波那契堆

   • 直接连接两个堆的根链表
   • 比较两个堆的最小指针，更新全局最小指针
   • 时间复杂度：实际O(1)，摊销O(1)

3. 删除最小元素（核心操作）

   • 步骤1：移除最小节点，将其所有子节点提升为根节点
   • 步骤2：执行Consolidate操作：
     • 创建度数数组（记录具有特定度数的树）
     • 遍历根链表，将相同度数的树合并（通过比较键值，使较大键值节点成为较小键值节点的子节点）
     • 合并后更新最小指针
   • 时间复杂度：实际O(D(n)+t(n))，摊销O(log n)，其中D(n)是最大度数

4. 减小键值操作

   • 减小指定节点的键值
   • 若违反最小堆性质且节点不在根链表，执行级联剪切：
     • 将节点提升为根节点
     • 若父节点已标记过，递归剪切父节点
     • 否则标记父节点（首次被剪切子节点）
   • 时间复杂度：摊销O(1)

优势与复杂度分析

• 插入/合并/减小键值：摊销O(1)
• 删除最小元素：摊销O(log n)
• 特别适合图算法（如Dijkstra、Prim）中频繁的减小键值操作

实现要点

1. 每个节点包含：键值、度数、子节点链表、父指针、标记位
2. 维护根链表（双向循环链表）和最小指针
3. Consolidate时使用度数数组避免重复合并

斐波那契堆通过惰性管理将开销分摊到后续操作，虽然常数因子较大，但在理论复杂度上达到了最优。