斐波那契堆（Fibonacci Heap） 描述 斐波那契堆是一种用于实现优先队列的数据结构，由一系列最小堆有序的树组成。它支持插入、查找最小值、合并、减小键值和删除最小值等操作，其中插入、合并和减小键值的时间复杂度为 摊还O(1) ，删除最小值的时间复杂度为 摊还O(log n) 。斐波那契堆在Dijkstra算法、Prim算法等图算法中有优化作用。 核心结构与性质 结构特点 ： 由多个最小堆有序的树（每棵树满足父节点≤子节点）组成。 使用 双向循环链表 连接根节点，便于快速合并。 每个节点包含：键值、子节点链表、父节点指针、标记（标记是否失去过子节点）。 关键性质 ： 最小节点指针 ：始终指向堆中最小键值的根节点。 最大度数限制 ：任何节点的子节点数（度数）不超过log₂n（通过合并操作保证）。 操作步骤与原理 1. 插入操作 步骤 ： a. 创建新节点，将其作为单独的树加入根链表。 b. 若新节点键值小于当前最小值，更新最小节点指针。 时间复杂度 ：实际O(1)，摊还O(1)。 2. 合并两个斐波那契堆 步骤 ： a. 将两个堆的根链表拼接成一个双向循环链表。 b. 比较两个堆的最小节点，更新最小节点指针。 时间复杂度 ：实际O(1)。 3. 提取最小值（删除最小值） 步骤 ： a. 移除最小节点，将其子节点加入根链表。 b. 合并度数相同的树 （核心优化）： 遍历根链表，使用辅助数组记录相同度数的树。 若发现两棵树度数相同，将键值较大的根链接为另一棵的子节点（类似二项堆的合并）。 c. 更新最小节点指针。 时间复杂度 ：摊还O(log n)。 4. 减小键值 步骤 ： a. 若减小后键值仍满足最小堆性质，直接更新。 b. 否则，将该节点剪切并加入根链表，同时检查父节点的标记： 若父节点未被标记，则标记它。 若父节点已被标记，递归剪切父节点（级联剪切）。 c. 更新最小节点指针。 时间复杂度 ：摊还O(1)。 5. 删除节点 通过减小键值至负无穷，再执行提取最小值操作实现。 为何摊还复杂度低？ 惰性合并 ：插入和合并时不立即整理树，推迟到提取最小值时统一处理。 级联剪切 ：通过标记机制避免节点过早失去子节点，保证树的平衡。 度数约束 ：合并度数相同的树确保每棵树节点数指数增长，从而限制最大度数。 示例演示（提取最小值） 假设根链表包含三棵树（度数均为0，键值分别为3、1、4）： 最小节点为1，移除它，其子节点（无）加入根链表。 合并度数相同的树：当前根节点（3、4）度数不同，无需合并。 更新最小节点为3。 若根链表有度数相同的树（如两棵度数1的树），则将键值大的根节点作为另一棵的子节点，生成一棵度数2的树。 总结 斐波那契堆通过惰性操作和级联剪切优化了优先队列的合并与键值更新，适用于需要频繁合并和修改的场景。尽管常数因子较大，其理论时间复杂度优势使其在算法优化中具有重要地位。