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

Question

Fibonacci heap数据结构的名称中带有单词“ Fibonacci”，但该数据结构中似乎没有任何内容使用斐波那契数字。根据维基百科的文章：

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

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

Answer 1

Fibonacci堆由遵循某些结构约束的不同“顺序”的较小堆排序树组成。斐波那契数列之所以出现是因为这些树的构造方式使得n阶树中至少有F _{n + 2}个节点，其中F _{n + 2}是（n + 2） nd斐波那契数。

要了解为什么这个结果是正确的，让我们先来看看斐波那契堆中的树是如何构造的。最初，只要将节点放入Fibonacci堆中，就会将其放入仅包含该节点的0阶树中。每当从Fibonacci堆中删除一个值时，Fibonacci堆中的某些树就会合并在一起，这样树的数量就不会太大。

[将树合并在一起时，斐波那契堆仅将相同顺序的树合并在一起。要将n阶的两棵树合并为n阶1的树，Fibonacci堆会采用两棵树中的任何一个具有比另一个更大的根值，然后使该树成为另一棵树的子代。这一事实的结果是顺序n的树总是正好有n个孩子。

斐波那契堆的主要吸引力在于它有效地支持了减少键（在摊销的O（1）中）。为了支持这一点，Fibonacci堆按如下方式实现了reduce-key：为了减少存储在某个节点中的值的键，将该节点从其父树上切下并视为其自己的单独树。发生这种情况时，其旧父节点的顺序将减少1。例如，如果订单4的树上有一个子树，则它会缩小为订单3的树，这是有道理的，因为树的订单应该是它包含的孩子数。

这样做的问题是，如果从同一棵树上砍掉太多树，则我们可能有一棵树的顺序很大，但其中包含的节点数量很少。只有在大订单的树木包含大量节点的情况下，才能保证Fibonacci堆的时间，并且，如果我们可以从树木中剪掉我们想要的任何节点，那么我们很容易陷入大订单的树木的情况。仅包含少量节点。

为了解决这个问题，斐波那契堆提出了一个要求-如果从一棵树上切下两个孩子，则必须从其父树上切下那棵树。这意味着构成斐波那契堆的树不会减小键会严重损坏它。

现在我们可以了解有关斐波那契数的部分。此时，我们可以对斐波那契堆中的树说以下内容：

• n阶树正好有n个孩子。
• n阶树是通过采用n-1阶的两棵树并使一个成为另一个的子代而形成的。
• [如果一棵树失去两个孩子，那棵树将从其父树上切下。

所以现在我们可以问-在这些假设下，您可以制造的最小的树是什么？

让我们尝试一些示例。只有一个可能的0阶树，它只是一个节点：

Smallest possible order 0 tree:      *

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

Smallest possible order 1 tree:      *
                                     |
                                     *

第二级最小的树怎么样？这就是事情变得有趣的地方。这棵树肯定必须有两个孩子，并且它将通过合并两个顺序为1的树而形成。因此，该树最初将有两个孩子-一个0的树​​和一个1的树。但是请记住-我们可以合并孩子后，将他们从树上砍掉！在这种情况下，如果我们切掉1阶树的子树，我们将剩下一棵有2个子树的树，这两个树都是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 n + 2

个节点，其中F _{n + 2}是第（n + 2）个斐波那契数。

那么为什么叫斐波那契堆呢？ 因为顺序n的每个树必须至少包含F _{n + 2}

个节点！

如果您有好奇心，the original paper on Fibonacci heaps

具有这些可能的最小树木的图片。看到它真漂亮！另外，请查看this CS Theory Stack Exchange Post，以获取有关Fibonacci堆树为何具有其大小的替代说明。

希望这会有所帮助！

Answer 2

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