斐波那契堆（Fibonacci Heap）

一、为什么学斐波那契堆？

Mermaid · 渲染中（下方为源码）

graph LR
  A[堆有序树集合] --> B[insert/merge O(1)]
  A --> C[decrease-key O(1) 摊还]
  A --> D[extract-min O(log n)]

斐波那契堆是"惰性"堆，把多次 decrease-key 的代价摊还到 extract-min。理论复杂度极佳：

这让 Dijkstra / Prim 的 O(E log V) 优化到 O(E + V log V)（用 decrease-key 版）。

Mermaid · 渲染中（下方为源码）

graph LR
  A[堆有序树集合] --> B[insert/merge O(1)]
  A --> C[decrease-key O(1) 摊还]
  A --> D[extract-min O(log n)]

斐波那契堆是"惰性"堆，把多次 decrease-key 的代价摊还到 extract-min。理论复杂度极佳：

这让 Dijkstra / Prim 的 O(E log V) 优化到 O(E + V log V)（用 decrease-key 版）。