为什么斐波纳契堆称为斐波那契堆？

Question

Fibonacci heap数据结构名称中包含“Fibonacci”这个词，但数据结构中似乎没有使用斐波纳契数字。根据维基百科的文章：

斐波那契堆的名称来自运行时分析中使用的斐波那契数。

这些斐波那契数如何在Fibonacci堆中出现？

Answer 1

斐波那契堆是由一系列不同“顺序”的较小堆排序树组成的，它们遵守特定的结构约束条件。 Fibonacci序列的出现是因为这些树的构造方式使得n阶树至少具有其中的节点，其中F _{n + 2}是第（n + 2）nd斐波纳契数。

为了明白为什么这个结果是真的，让我们先看看斐波那契堆中的树是如何构造的。最初，无论何时将一个节点放入Fibonacci堆中，它都将放入只包含该节点的0阶树中。每当从斐波那契堆中删除一个值时，斐波那契堆中的一些树会聚合在一起，这样树的数量不会变得太大。

将树组合在一起时，斐波那契堆只将相同顺序的树组合在一起。为了将n棵树中的两棵树合并到一棵n + 1棵树中，斐波那契堆使得两棵树中的一棵具有比另一棵更大的根值，然后使该树成为另一棵树的子树。这个事实的一个结果是，n阶树的总是正好有n个孩子。

斐波那契堆的主要吸引力是它有效地支持减少键（在摊还O（1））。为了支持这一点，斐波那契堆实现了递减键，如下所示：为了减少存储在某个节点中的值的键值，该节点从其父树中被截断并被视为它自己的单独树。发生这种情况时，其旧父节点的顺序减1。例如，如果一个订单4的树有一个孩子被剪下来，它缩小到3棵树的顺序，这很有意义，因为树的顺序应该是它包含的孩子的数量。

这样做的问题是，如果太多的树从同一棵树中切断，我们可能会有一棵大小不等的树，但其中包含的节点数很少。斐波那契堆的时间保证只有在大订单的树含有大量节点的情况下才有可能，并且如果我们可以从树中剪切任何我们想要的节点，我们可以很容易地进入一个情况，只包含少量的节点。

为了解决这个问题，斐波那契堆提出了一个要求 - 如果你从一棵树上切下两个孩子，你必须依次从它的父亲切下那棵树。这意味着形成Fibonacci堆的树不会因减键而受到太严重的破坏。

现在我们可以看到关于斐波那契数的部分。此时，我们可以对Fibonacci堆中的树进行如下说明：

• 一棵n阶的树恰好有n个孩子。
• 秩序n的树是通过采取n-1阶的两棵树并使其成为另一棵的子树而形成的。
• 如果一棵树失去两个孩子，那棵树就会从其父母身上割下。

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

让我们尝试一些例子。只有一个的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棵2阶树合并在一起而形成。然后，我们将尝试尽可能多地去掉这棵3阶树的子树。当它被创建时，树具有次序为2,1和0的子树。我们不能从0号树中删除，但是我们可以从2号树和1号树中砍掉一个孩子。如果我们这样做，我们留下了一棵树，有三个孩子，1阶一个和两个顺序2：

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

现在，我们可以发现一个模式。最小可能的order-（n + 2）树形成如下：首先创建一个正常顺序（n + 2）树，它具有顺序n + 1，n，n-1，...，2 ，1，0。然后，通过从这些树上切下节点，尽可能减小这些树，而不会从同一节点切割两个孩子。这样就留下了一棵树，其中有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 _{n + 2}是第（n + 2）nd斐波纳契数。

那么为什么它被称为斐波那契堆？ 因为每个n阶树必须至少有F _{n + 2}个节点！

如果您好奇，the original paper on Fibonacci heaps有这些最小可能的树的图片。这是相当漂亮的看到！

希望这会有所帮助！

Answer 2

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

树结构实现了O（log n）运行时间，因为它们能够根据它们的高度存储指数数量的项目。二叉树可以存储2^h，三元树可以存储3^h等等。

x可以小于2吗？当然可以！只要x> 1，我们仍然可以达到日志运行时间并能够存储指数级大量项目的高度。但我们如何建立这样一棵树？斐波那契堆是一个数据结构，其中x≈1.62，或Golden Ratio。每当我们遇到黄金比例时，斐波纳契数字都会潜伏在某处...

斐波那契堆实际上是一片树林。经过一个叫做“合并”的过程后，这些树中的每一棵都拥有2个精确幂的项目的明显数量。例如，如果斐波那契堆有15个项目，则它将有4棵树保持1,2,4和8项目分别寻找像这样的：

详细信息“整合”的过程是不相关的，但它在本质上基本保持在相同程度的森林unioning树，直到所有的树有不同程度（尝试cool visualization看这些树如何建成）。正如你可以写出任意n作为2的精确幂的和，很容易想象斐波那契堆的树会如何为任何n看起来像。好吧，到目前为止，我们仍然没有看到任何与斐波纳契数字的直接连接。他们在哪里照片？它们实际上出现在非常特殊的情况下，这也是为什么斐波那契堆为DECREASE-KEY操作提供O（1）时间的关键。当我们减少一个键时，如果新键仍然大于父键，那么我们不需要做任何事情，因为min-heap属性没有被违反。但是，如果不是这样，我们不能将较小的孩子留在较大的父母身上，所以我们需要削减它的子树，并从中挖出一棵新树。显然，我们无法继续为每次删除操作，因为否则我们会得到高度过大且不再具有指数项的树，这意味着提取操作不再需要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.我们在此有斐波那契数列！由于Fibonacci序列是指数型的，每棵树仍然保留着指数数量的项目，因此管理为EXTRACT-MIN操作具有O（log n）运行时间。但请注意，DECREASE-KEY现在只需要O（1）。另一个很酷的事情是，你可以将任何数字表示为斐波那契数的总和。例如，32 = 21 + 8 + 3这意味着如果你需要在Fibonacci堆中保存32个项目，你可以使用3棵树分别持有21,8和3项。但是“合并”过程不会生成具有斐波那契数量节点的树。它们只发生在DECREASE-KEY或DELETE发生这种最坏情况时。

延伸阅读

• Binomial Heap - 斐波那契堆基本上是懒惰二项堆。这是一个很酷的数据结构，因为它显示了将指数项存储在树中除二进制堆以外的高度的另一种方式。
• Intuition behind Fibonacci Heaps任何想要了解斐波那契堆为核心的人都必读。对于这个问题，教科书通常要么太浅而且太混乱，但这个答案的作者已经把它放在了手中。