斐波那契堆|集1（简介）

堆主要用于实现优先级队列。我们在之前的帖子中讨论过以下堆。

二进制堆 二项式堆

就时间复杂度而言，斐波那契堆优于二进制堆和二项式堆。

下面是 摊销时间复杂性 属于 斐波那契堆 .

1) Find Min:      Θ(1)     [Same as both Binary and Binomial]2) Delete Min:    O(Log n) [Θ(Log n) in both Binary and Binomial]3) Insert:        Θ(1)     [Θ(Log n) in Binary and Θ(1) in Binomial]4) Decrease-Key:  Θ(1)     [Θ(Log n) in both Binary and Binomial]5) Merge:         Θ(1)     [Θ(m Log n) or Θ(m+n) in Binary and                            Θ(Log n) in Binomial]

喜欢 二项式堆 ，Fibonacci Heap是具有min Heap或max Heap属性的树的集合。在Fibonacci堆中，树可以有任何形状，甚至所有树都可以是单个节点（这与二项式堆不同，在二项式堆中，每棵树都必须是二项式树）。

下面是一个Fibonacci堆的例子 在这里 .

其中Heap（Fibonacci的最小值是指向树的根的指针）。所有树根都使用循环双链表连接，因此所有树根都可以使用单个“min”指针访问。

其主要思想是以“懒惰”的方式执行操作。例如，合并操作只是链接两个堆，插入操作只是添加一个具有单个节点的新树。提取最小值的操作是最复杂的操作。它会延迟树木的加固工作。这使得delete也变得复杂，因为delete首先将键减为负无穷大，然后调用extract minimum。

下面是一些关于斐波那契堆的有趣事实

1. Prim降低了Dijk算法的时间复杂度，降低了Dijk算法的重要性。对于二进制堆，这些算法的时间复杂度为O（VLogV+ELogV）。如果使用斐波那契堆，那么时间复杂度将提高到O（VLogV+E）
2. 尽管Fibonacci堆在时间复杂度方面看起来很有前途，但人们发现它在实践中很慢，因为隐藏常数很高（源代码） 维基 ).
3. Fibonacci堆之所以被称为Fibonacci堆，主要是因为在运行时分析中使用了Fibonacci数。此外，Fibonacci堆中的每个节点的度数最多为O（logn），并且在度数为k的节点中根的子树的大小至少为F _k+2 ，其中F _K 是第k个斐波那契数。

我们将很快详细讨论斐波那契堆操作。

本文由 希瓦姆 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。