斐波那契堆

斐波那契数列由0和1开始,之后的斐波那契数就是由之前的两数相加而得出,比如  0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233

斐波那契堆(Fibonacci heap)是计算机科学中树的集合。它比二项堆具有更好的平摊分析性能,可用于实现合并优先队列。不涉及删除元素的操作有O(1)的平摊时间。 Extract-Min和Delete的数目和其它相比,较小时效率更佳。稠密图每次decrease key只要O(1)的平摊时间,和二项堆的O(lg n)相比是巨大的改进

斐波那契堆是由一组最小堆有序树构成的。每个节点的度数为其子节点的数目。树的度数为其根节点的度数

斐波那契堆中的树都是有根的但是无序


具体操作参考:

wiki-斐波那契

geeksforgeeks-fibonacci-heap

上一篇: 二项堆
下一篇: 无
作者邮箱: 203328517@qq.com