斐波那契堆Fibonacci Heap故事文件078斐波那契堆算法中的“懒惰”天才5W1H维度描述What是什么斐波那契堆是一种基于循环双向链表与懒惰合并策略的优先队列数据结构支持摊销 O(1) 的插入与 decrease-key以及摊销 O(log n) 的 extract-min。Who谁提出Michael L. Fredman 与 Robert E. Tarjan 于 1987 年提出发表于Journal of the ACM是当时最优的优先队列理论界。When何时适用在需要大量 decrease-key 操作的图算法Dijkstra、Prim中斐波那契堆可将整体复杂度降至 O(V log V E)远优于二叉堆的 O((VE) log V)。Where出处TAOCP 第3卷排序与查找Fredman-Tarjan 1987 原论文另见 CLRS 第19章。Why为什么重要它证明了通过延迟工作lazy consolidation可以在摊销意义下突破朴素实现的复杂度下界是摊销分析的经典教材案例。How如何工作根链表循环双向链表收集所有堆树的根insert 直接追加到根链表extract-min 时才触发 consolidate合并同 degree 的树类似二进制加法decrease-key 通过 cut cascading-cut 维护堆序性质mark 位控制级联切割的次数。需求定义功能需求ID需求F1fib_heap_insert(heap, key)— 将键值 key 插入堆返回节点指针摊销 O(1)。F2fib_heap_find_min(heap)— 返回当前最小键值O(1)空堆返回 -1。F3fib_heap_extract_min(heap)— 删除并返回最小键值触发 consolidate摊销 O(log n)空堆返回 -1。F4fib_heap_decrease_key(heap, node, new_key)— 将节点 key 减小为 new_key摊销 O(1)new_key 原 key 时打印警告并忽略。F5fib_heap_free(heap)— 释放所有节点与堆结构无内存泄漏。非功能需求节点结构{key, degree, mark, parent, child, left, right}parent/child/left/right 均为FibNode *。使用循环双向链表管理根链表与子节点链表。consolidate 中 degree 数组大小上界取 64足以覆盖 2^64 个节点。不使用math.h/-lm纯 C99无平台扩展。编译命令gcc -stdc99 -Wall fibonacci_heap.c -o fibonacci_heap零警告零错误。验收标准编号测试场景期望结果T1插入 [5, 3, 7, 1, 4]调用find_min()返回 1T2同上后连续 5 次extract_min()依次返回 1, 3, 4, 5, 7严格升序T3插入 10, 20, 30将 30 decrease_key 为 5调用find_min()返回 5T4T3 基础上extract_min()返回 5T5逆序插入 50…1共50个依次extract_min()直至堆空输出严格升序 1…50最后一次 extract_min 返回 -1T6空堆调用extract_min()返回 -1程序不崩溃T7空堆调用find_min()返回 -1程序不崩溃所有测试通过后main返回 0任意失败返回 1。