斐波那契堆堆数据结构由树林组成 / 维基百科,自由的 encyclopedia 斐波那契堆(英语:Fibonacci heap)是电脑科学中树的集合。它比二项堆具有更好的平摊分析性能,可用于实现合并优先队列。不涉及删除元素的操作有 O ( 1 ) {\displaystyle O(1)} 的平摊时间。 Extract-Min和Delete的数目和其它相比,较小时效率更佳。稠密图每次decrease key只要 O ( 1 ) {\displaystyle O(1)} 的平摊时间,和二项堆的 O ( l o g n ) {\displaystyle O(logn)} 相比是巨大的改进。 Quick Facts 斐波那契堆, 类型 ...斐波那契堆类型堆发明时间1984年发明者迈克尔·弗雷德曼、罗伯特·塔扬用大O符号表示的时间复杂度算法 平均 最差插入 Θ ( 1 ) {\displaystyle \Theta (1)} 寻找最小值 Θ ( 1 ) {\displaystyle \Theta (1)} 删除最小值 O ( log n ) {\displaystyle O(\log n)} 减小键值 Θ ( 1 ) {\displaystyle \Theta (1)} 合并 Θ ( 1 ) {\displaystyle \Theta (1)} Close 斐波纳契堆于1984年由迈克尔·弗雷德曼与罗伯特·塔扬提出,1987年公开发表。[1]名字来源于运行时分析使用的斐波那契数。
斐波那契堆(英语:Fibonacci heap)是电脑科学中树的集合。它比二项堆具有更好的平摊分析性能,可用于实现合并优先队列。不涉及删除元素的操作有 O ( 1 ) {\displaystyle O(1)} 的平摊时间。 Extract-Min和Delete的数目和其它相比,较小时效率更佳。稠密图每次decrease key只要 O ( 1 ) {\displaystyle O(1)} 的平摊时间,和二项堆的 O ( l o g n ) {\displaystyle O(logn)} 相比是巨大的改进。 Quick Facts 斐波那契堆, 类型 ...斐波那契堆类型堆发明时间1984年发明者迈克尔·弗雷德曼、罗伯特·塔扬用大O符号表示的时间复杂度算法 平均 最差插入 Θ ( 1 ) {\displaystyle \Theta (1)} 寻找最小值 Θ ( 1 ) {\displaystyle \Theta (1)} 删除最小值 O ( log n ) {\displaystyle O(\log n)} 减小键值 Θ ( 1 ) {\displaystyle \Theta (1)} 合并 Θ ( 1 ) {\displaystyle \Theta (1)} Close 斐波纳契堆于1984年由迈克尔·弗雷德曼与罗伯特·塔扬提出,1987年公开发表。[1]名字来源于运行时分析使用的斐波那契数。