首页 > 代码库 > 斐波那契堆
斐波那契堆
斐波纳契堆（Fibonacci Heap）于 1984 年由 Michael L. Fredman 与 Robert E. Tarjan 提出，1987 年公开发表，名字来源于运行时分析所使用的斐波那契数。
斐波那契堆同二项堆（Binomial Heap）一样，也是一种可合并堆（Mergeable Heap）。与二项堆一样，斐波那契堆是由一组最小堆有序树构成，但堆中的树并不一定是二项树。与二项堆中树都是有序的不同，斐波那契堆中的树都是有根而无序的。
实际上，斐波那契堆松散地基于二项堆。如果不对斐波那契堆做任何 DECREASE-KEY 或 DELETE 操作，则堆中每棵树就和二项树一样。但是如果执行这两种操作，在一些状态下必须要破坏二项树的特征，比如DECREASE-KEY 或 DELETE 后，有的树高为 k，但是结点个数却少于 2k。这种情况下，堆中的树不是二项树。
斐波那契堆的优势是：不涉及删除元素的操作仅需要 O(1) 的平摊运行时间。
| Operation | Binary | 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 操作。
斐波那契堆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。