19

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

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

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

4

2 回答 2

23

斐波那契堆由一组较小的堆排序树组成，这些树具有不同的“顺序”，它们服从某些结构约束。斐波那契数列的出现是因为这些树的构造方式使得 n 阶树中至少有 F n+2个节点，其中 F n+2是第 (n + 2) 个斐波那契数。

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

将树组合在一起时，斐波那契堆仅将相同顺序的树组合在一起。要将两棵 n 阶树组合成 n + 1 阶树，斐波那契堆取两棵树中的哪棵树的根值大于另一棵树，然后使该树成为另一棵树的子树。这一事实的一个结果是n 阶的树总是恰好有 n 个孩子。

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

这样做的问题是，如果从同一棵树上剪掉太多树，我们可能会得到一棵树的顺序很大但包含的节点数量很少。斐波那契堆的时间保证只有在具有大订单的树包含大量节点时才有可能，并且如果我们可以从树中删除我们想要的任何节点，我们很容易陷入这样一种情况，即具有大订单的树仅包含少量节点。

为了解决这个问题，斐波那契堆提出了一个要求——如果你从一棵树上砍下两个孩子，你必须反过来从它的父树上砍下那棵树。 这意味着形成斐波那契堆的树不会被减少键严重损坏。

现在我们可以进入关于斐波那契数的部分。在这一点上，我们可以对斐波那契堆中的树说以下内容：

  • 一棵 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 阶树合并在一起形成的。然后我们会尝试尽可能多地剪掉这棵 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)nd 斐波那契数。

那么为什么叫斐波那契堆呢？ 因为每棵 n 阶树中必须至少有 F n+2个节点！

如果你很好奇，关于斐波那契堆的原始论文有这些可能最小的树的图片。很漂亮！另外，查看这篇 CS Theory Stack Exchange Post以获得关于为什么 Fibonacci 堆树具有它们的大小的替代解释。

希望这可以帮助！

于 2013-01-15T07:56:21.983 回答
5

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

树结构的运行时间为 O(log n)，因为它们能够根据高度存储指数数量的项目。二叉树可以存储 2^h，三叉树可以存储 3^h，以此类推 x^h 作为通用案例。

x 可以小于 2 吗？当然可以！只要 x > 1，我们仍然可以实现日志运行时间，并且能够为其高度存储指数级大量项目。但是我们如何建造这样一棵树呢？斐波那契堆是 x ≈ 1.62 或黄金比例的数据结构。每当我们遇到黄金分割率时，总会有斐波那契数字潜伏在某处……

斐波那契堆实际上是一片树林。在一个称为“合并”的过程之后，这些树中的每一个都持有不同数量的项目，这些项目是 2 的精确幂。例如，如果您的斐波那契堆有 15 个项目，那么它将有 4 棵树分别持有 1、2、4 和 8项目分别看起来像这样：

在此处输入图像描述

“合并”过程的细节无关紧要，但本质上它基本上保持联合森林中相同程度的树木，直到所有树木都具有不同的程度（尝试一个很酷的可视化来查看这些树木是如何构建的）。由于您可以将任何 n 写为 2 的精确幂的总和，因此很容易想象对于任何 n，斐波那契堆的合并树会是什么样子。

好的，到目前为止，我们仍然没有看到与斐波那契数字有任何直接联系。他们在哪里出现？它们实际上出现在非常特殊的情况下，这也是为什么斐波那契堆可以为 DECREASE-KEY 操作提供 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. 我们这里有一个斐波那契数列！

由于斐波那契数列是指数的，每棵树仍然保留指数数量的项目，因此 EXTRACT-MIN 操作的运行时间为 O(log n)。但是请注意，DECREASE-KEY 现在只需要 O(1)。另一件很酷的事情是，您可以将任何数字表示为斐波那契数的总和。例如，32 = 21 + 8 + 3 这意味着如果您需要在 Fibonacci 堆中保存 32 个项目，您可以使用分别容纳 21、8 和 3 个项目的 3 棵树来实现。然而，“整合”过程不会产生具有斐波那契节点数的树。它们仅在发生这种更糟糕的 DECREASE-KEY 或 DELETE 情况时才会发生。

进一步阅读

  • 二项式堆- 斐波那契堆本质上是惰性二项式堆。这是一个很酷的数据结构，因为它显示了一种在树中存储指数项的不同方式，因为它的高度不同于二叉堆。
  • 斐波那契堆背后的直觉任何想要了解斐波那契堆核心的人都需要阅读。教科书通常在这个主题上要么太浅，要么太杂乱，但这个 SO 答案的作者已经把它钉牢了。
于 2014-12-27T09:13:20.617 回答