Fibonacci heap数据结构的名称中带有单词“ Fibonacci”，但数据结构中似乎没有任何内容使用斐波那契数字。根据维基百科的文章：
Fibonacci堆的名称来自运行时间分析中使用的Fibonacci数字。
这些斐波那契数在斐波那契堆中如何产生？
最佳答案
斐波那契堆由遵循某些结构约束的不同“顺序”的较小堆排序树的集合组成。斐波那契数列之所以出现，是因为这些树的构建方式使得n阶树中至少有Fn + 2个节点，其中Fn + 2是第（n + 2）个斐波那契数。
为了弄清楚为什么这个结果是正确的，让我们从如何构造斐波那契堆中的树开始。最初，只要将节点放入Fibonacci堆中，就会将其放入仅包含该节点的0阶树中。每当从Fibonacci堆中删除某个值时，Fibonacci堆中的某些树就会合并在一起，这样树的数量就不会太大。
将树合并在一起时，斐波那契堆只会将相同顺序的树合并在一起。要将n阶的两棵树合并为n阶1的树，Fibonacci堆将采用两棵树中的任何一个具有比另一个更大的根值，然后将该树作为另一个树的子代。这一事实的结果是，顺序为n的树总是恰好有n个子代。
Fibonacci堆的主要吸引力在于，它有效地支持了减少键（在摊销O（1）中）。为了支持这一点，斐波那契堆按如下方式实现了reduce-key：为了减少存储在某个节点中的值的键，将该节点从其父树上切下并视为其自己的单独树。发生这种情况时，其旧父节点的顺序将减少1。例如，如果订单4的树上有一个子树，则它会缩小为订单3的树，这是有道理的，因为树的订单应该是它包含的孩子数。
这样做的问题是，如果从同一棵树上砍下太多树，则我们可能有一棵树的顺序较大，但其中包含的节点数量很少。只有在大订单的树木包含大量节点的情况下，才能保证Fibonacci堆的时间，并且，如果我们可以从树木中剪掉我们想要的任何节点，那么我们很容易陷入大订单的树木的情况。仅包含少量节点。
为了解决这个问题，斐波那契堆提出了一个要求-如果您从一棵树上砍下两个孩子，则必须从其父树上砍下那棵树。这意味着形成Fibonacci堆的树不会受到减键的严重破坏。
现在我们可以了解有关斐波那契数的部分。在这一点上，我们可以对斐波那契堆中的树说以下话：
n阶树正好有n个孩子。
n阶树是通过采用n-1阶的两棵树并使一个成为另一个的子代而形成的。
如果一棵树失去两个孩子，则从其父树上砍掉该树。
所以现在我们可以问-在这些假设下，您可以制造的最小树木是什么？
让我们尝试一些例子。只有一个可能的0阶树，它只是一个节点：
Smallest possible order 0 tree: *
最小的1阶可能树必须至少是一个带有子节点的节点。我们可以制作的最小子节点是一个最小的order-0树作为子节点的单节点，该树是：
Smallest possible order 1 tree: *
|
*
那么最小二阶树呢？这就是事情变得有趣的地方。这棵树肯定必须有两个子代，它将通过合并两个顺序为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
如果您会注意到，这恰好是斐波那契数列的两个位置的偏移量。换句话说，这些树中的每一个必须至少具有Fn + 2个节点，其中Fn + 2是第（n + 2）个斐波那契数。
那么为什么叫斐波那契堆呢？因为n阶的每个树必须至少包含Fn + 2个节点！
如果您感到好奇，the original paper on Fibonacci heaps会提供这些最小树木的图片。看到它真漂亮！另外，请查看this CS Theory Stack Exchange Post以获得有关为何斐波那契堆树具有其大小的替代说明。
希望这可以帮助！
关于math - 为什么斐波那契堆称为斐波那契堆？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14333314/