首页 > 代码库 > 斐波那契堆

斐波那契堆

斐波纳契堆(Fibonacci Heap)于 1984 年由 Michael L. Fredman 与 Robert E. Tarjan 提出,1987 年公开发表,名字来源于运行时分析所使用的斐波那契数。

斐波那契堆同二项堆(Binomial Heap)一样,也是一种可合并堆(Mergeable Heap)。与二项堆一样,斐波那契堆是由一组最小堆有序树构成,但堆中的树并不一定是二项树。与二项堆中树都是有序的不同,斐波那契堆中的树都是有根而无序的。

实际上,斐波那契堆松散地基于二项堆。如果不对斐波那契堆做任何 DECREASE-KEY 或 DELETE 操作,则堆中每棵树就和二项树一样。但是如果执行这两种操作,在一些状态下必须要破坏二项树的特征,比如DECREASE-KEY 或 DELETE 后,有的树高为 k,但是结点个数却少于 2k。这种情况下,堆中的树不是二项树。

斐波那契堆的优势是:不涉及删除元素的操作仅需要 O(1) 的平摊运行时间。

OperationBinary
Binomial
Fibonacci
Pairing
Brodal
Rank-pairing
find-minΘ(1)Θ(1)Θ(1)Θ(1)Θ(1)Θ(1)
delete-minΘ(log n)Θ(log n)O(log n)
O(log n)
O(log n)O(log n)
insertΘ(log n)Θ(1)
Θ(1)Θ(1)Θ(1)Θ(1)
decrease-keyΘ(log n)Θ(log n)Θ(1)
Unknown
Θ(1)Θ(1)
mergeΘ(mlog(n+m))
O(log n)
Θ(1)Θ(1)Θ(1)Θ(1)

对于斐波那契堆上的各种可合并操作,关键思想是尽可能久地将工作推后。例如,当向斐波那契堆中插入新结点或合并两个斐波那契堆时,并不去合并树,而是将这个工作留给 EXTRACT-MIN 操作。

斐波那契堆