斐波纳契堆（Fibonacci Heap）于 1984 年由 Michael L. Fredman 与 Robert E. Tarjan 提出，1987 年公开发表，名字来源于运行时分析所使用的斐波那契数。
斐波那契堆的优势是：不涉及删除元素的操作仅需要 O(1) 的平摊运行时间。
Operation
find-min
Θ(1)
delete-min
Θ(log n)
O(log n)
insert
decrease-key
merge
对于斐波那契堆上的各种可合并操作，关键思想是尽可能久地将工作推后。例如，当向斐波那契堆中插入新结点或合并两个斐波那契堆时，并不去合并树，而是将这个工作留给 EXTRACT-MIN 操作。
<a></a>
<a>本文转自匠心十年博客园博客，原文链接：http://www.cnblogs.com/gaochundong/p/fibonacci_heap.html，如需转载请自行联系原作者</a>