为什么叫斐波那契堆斐波那契堆？(Why is a Fibonacci heap called a F

的斐波那契堆数据结构在其名称中的“黄金分割”，但没有在数据结构似乎使用斐波那契数。根据维基百科的文章：

斐波那契堆的名字来自其在运行时间分析中使用斐波那契数。

如何将这些斐波那契数的斐波那契堆产生的呢？

Answer 1:

斐波那契堆是由服从一定的结构性制约因素的不同的“订单”小堆排序树的集合。斐波纳契数列的产生是因为这些树的方式构造，使得阶数n的树中有至少F 2 _{N + 2}个节点，其中，F _{n + 2}的第（n + 2）Fibonacci数。

要知道为什么这个结果是真实的，让我们开始讨论怎样在斐波那契堆树木构造。最初，当一个节点被放入一个斐波那契堆，将其放入的顺序0树只包含该节点。每当值从斐波那契堆中取出，有的在斐波那契堆的树木被合并在一起，使得树木的数量不会增长太大。

当结合在一起的树木，斐波那契堆只有结合了同阶的树木一起。为了秩序两棵树结合n为进的n阶+ 1一棵树，斐波那契堆取两棵树取其具有比其他更大的根值，然后让该树的树其他的孩子。这一事实的一个结果是n阶的树木总是恰好n孩子 。

斐波那契堆的主要吸引力在于它有效地支持的减少键（在摊销O（1））。为了支持这一点，斐波那契堆实现减少键如下：以降低存储在某些节点中的值的密钥，则该节点从它的父树切割并作为它自己的单独的树进行处理。发生这种情况时，其旧的父节点的顺序是由一个下降。例如，如果一个订单4棵树从中切开一个孩子，它缩小到3阶树，因为树的顺序应该是它包含的儿童人数这是有道理的。

有这样做的问题是，如果有太多的树木从同树断了，我们可能有一棵树，一个大订单，但它包含一个非常小数量的节点。斐波那契堆的时间保证是唯一可能的，如果有大批量订单树包含节点数量庞大，如果我们可以只是削减我们会从树上喜欢的任何节点，我们可以很容易地得到进入的情况下有一个巨大的顺序树只包含少量的节点。

为了解决这个问题，斐波那契堆做一个要求- 如果你从砍一棵树的两个孩子，你要反过来砍这棵树从其父。 这意味着，形成一个斐波那契堆树木也不会太严重降低通过钥匙损坏。

现在，我们可以得到约斐波那契数的部分。在这一点上，我们可以说有关在斐波那契堆树木以下内容：

n阶树有恰好n孩子。
1，使一个的另一个孩子 - n阶树被采取的n阶两棵树形成。
如果一棵树失去了两个孩子，那棵树是从其父切掉。

所以，现在我们可以问 - 什么是最小可能的树，你可以在这些假设下做什么呢？

让我们尝试了一些例子。只有一个的顺序0，这是一个公正的一个节点可能的树：

Smallest possible order 0 tree:      *

1阶最小的树将必须至少有一个子节点。最小的孩子可能我们可以做是最小订单0树作为一个孩子，这是该树中的单个节点：

Smallest possible order 1 tree:      *
                                     |
                                     *

怎么样的顺序2最小的树？这就是事情变得有趣。这棵树肯定有两个孩子，并会通过的顺序1.因此两棵树合并在一起而形成，树最初将有两个孩子 - 的顺序0一棵树的顺序1.树但是，请记住 - 我们可以切去从树上孩子们将它们合并后！在这种情况下，如果我们切掉1阶树的孩子，我们就只剩下有两个孩子，这两者都是顺序0树树：

Smallest possible order 2 tree:      *
                                    / \
                                   *   *

怎么样3阶？和以前一样，这棵树将取决于订单2.两棵树合并在一起进行，我们会再尝试切掉尽可能多的这个订单3树尽可能的子树。当它的创建，树有订单2，1的子树，和0。我们不能从0阶树切掉，但我们可以从订单2和1阶树砍单的孩子。如果我们这样做，我们留下了一个有三个孩子，1阶一个和两个2阶一棵树：

 Smallest possible order 3 tree:       *
                                      /|\
                                     * * *
                                     |
                                     *

现在，我们可以发现一个模式。尽可能小的命令 - （N + 2）树将形成如下：通过建立正常秩序（N + 2）树，有订单的儿童N + 1开始，N，N - 1，...，2 ，1，0。然后，使这些树木被切掉从他们的节点，而不从同一节点切割两个孩子尽可能小。这使得与订单的孩子树N，N - 2，...，1,0和0。

现在我们可以写一个递推关系，试图确定有多少个节点，在这些树木。如果我们这样做，我们得到以下内容，其中NC（n）表示节点，可能是在n阶树的最小数：

NC(0) = 1
NC(1) = 2
NC(n + 2) = NC(n) + NC(n - 1) + ... + NC(1) + NC(0) + NC(0) + 1

在这里，最终+1占根节点本身。

如果我们扩大了这些条款，我们得到如下：

NC(0) = 1
NC(1) = 2
NC(2) = NC(0) + NC(0) + 1 = 3
NC(3) = NC(1) + NC(0) + NC(0) + 1 = 5
NC(4) = NC(2) + NC(1) + NC(0) + NC(0) + 1 = 8

如果你会发现，这正是斐波纳契数列由两个位置偏移。换言之，每个树的必须具有至少F 2 _{N + 2个}节点它们，其中F _{n + 2}的第（n + 2）Fibonacci数。

那么，为什么要叫一个斐波那契堆？ 由于n阶的每棵树都必须有至少_{FN + 2个}节点吧！

如果你很好奇， 在斐波那契堆原纸具有这些最小的树的照片。这是非常漂亮的，看！

希望这可以帮助！

Answer 2:

我想举一个直观的解释，我自己有一个“啊哈！” 时刻用。

树形结构实现O（log n）的运行时将因为它们能够存储在他们的高度方面的项目数量指数。二叉树可以存储2 ^ h时，三进制树可存储3 1 H等对于x ^ H作为通用的情况。

能X小于2？当然可以！只要X> 1，我们仍然实现日志的运行时间和存储成倍大量项目是因其高度的能力。但是，我们如何建立这样的树？斐波那契堆是一种数据结构，其中x≈1.62，或黄金比率。每当我们遇到的黄金比例，有斐波那契数潜伏的地方...

斐波那契堆其实是一片森林。所谓的“整合”的过程后，每个树认为是2例如确切权力项目的重复计数，如果你的斐波那契堆有15个项目，这将有4棵持有1，2，4和8项目分别看起来像这样：

“整合”的过程的细节是不相关的，但它在本质上基本保持unioning树木的相同程度的森林中，直到所有的树有不同的程度（尝试酷可视化，看看这些树是如何被构建的）。正如你可以写任何N作为2精确功率的总和，很容易想象如何为斐波那契堆合并树看起来像对任意n。

OK，到目前为止，我们仍然没有看到斐波那契数的任何直接连接。他们在哪里进来的图片？他们实际上出现在非常特殊的情况，这也是为什么斐波那契堆可以提供O（1）时间减少用按键操作的关键。当我们减少的一个关键，如果新的关键仍然是比父母的关键更大然后我们并不需要，因为最小堆财产不受侵犯做别的。但是，如果不是，那么我们不能离开小的孩子下更大父埋，所以我们需要削减它的子树，同时使新树出来。显然，我们不能继续这样做对每个删除，否则，我们将结束与过于高大，不再有指数的项目，这意味着用于提取操作没有更多的O（log n）的时间树。所以，问题是什么规则我们可以建立这样的树仍然有其高度指数的项目？聪明的见解是这样的：

We will allow each parent to loose up to one child. If there is a subsequent attempt to remove another child from same parent then we will cut that parent also out of that tree and put it in root list as tree of 1.

上面的规则确保树木仍然有它，即使在最坏的情况下高度指数项目。什么是最坏的情况？当我们让每个父母失去一个孩子出现更糟的情况。如果父母有> 1点的孩子，我们必须选择其中一个摆脱。在这种情况下，让我们用最大的子树摆脱孩子。因此，在上图中，如果你这样做，对于每个家长，您将有大小1，1，2和3在这里看到一个模式的树木？只是为了好玩，增加新树的4阶（即16项）上图中，你猜你会只剩下运行此规则对于每个父后：5，我们这里有一个斐波那契序列！

如斐波纳契数列是指数的，每个树仍保留项指数数量，从而设法具有O（log n）的运行时间EXTRACT-MIN操作。不过，请注意DECREASE-KEY现在只需要O（1）。另外一个很酷的事情是，你可以代表任何数量，斐波那契数的总和。例如，32 = 21 + 8 + 3，如果你需要保持在斐波那契堆32项，这意味着，可以这样做，使用3-树木分别保持21，图8和3项。不过“合并”过程中不产生与节点的斐波那契数树。他们只发生在DECREASE-KEY的这种最坏情况或DELETE发生。

延伸阅读