为什么Fibonacci堆称为Fibonacci堆？
tem*_*def 17 math fibonacci data-structures fibonacci-heap
的斐波那契堆数据结构在其名称中的"黄金分割",但没有在数据结构似乎使用斐波那契数.根据维基百科的文章:
Fibonacci堆的名称来自Fibonacci数字,用于运行时间分析.
Fibonacci堆中如何出现这些Fibonacci数？
tem*_*def 20
Fibonacci堆由一组遵循某些结构约束的不同"顺序"的较小堆排序树组成.Fibonacci序列的产生是因为这些树的构造方式使得n阶树在其中至少有F n + 2个节点,其中F n + 2是(n + 2)nd Fibonacci数.
要了解为什么这个结果是真的,让我们首先看看Fibonacci堆中的树是如何构造的.最初,只要将节点放入Fibonacci堆中,就会将其放入包含该节点的0阶树中.每当从Fibonacci堆中移除一个值时,Fibonacci堆中的一些树就会合并在一起,这样树的数量就不会变得太大.
将树组合在一起时,Fibonacci堆只将相同顺序的树组合在一起.为了将n阶n的树组合成n + 1阶的树,Fibonacci堆取两棵树中的哪一个具有比另一棵树更大的根值,然后使该树成为另一棵树的子树.这个事实的一个结果是n阶树总是有n个孩子.
Fibonacci堆的主要吸引力在于它有效地支持减少密钥(在摊销的O(1)中).为了支持这一点,Fibonacci堆实现了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: *
|
*
那2号最小的树怎么样？这是事情变得有趣的地方.这棵树当然必须有两个孩子,它将通过将两棵树合并在一起而形成.因此,树最初会有两个孩子 - 一棵0号树和一棵1号树.但请记住 - 我们可以合并后将孩子从树上切掉!在这种情况下,如果我们切掉了1阶树的子节点,我们将留下一棵带有两个孩子的树,这两个孩子都是0阶的树:
Smallest possible order 2 tree: *
/ \
* *
订单3怎么样？和以前一样,这棵树将通过合并两个2阶树的树来制作.然后我们会尝试尽可能多地删除这个3阶树的子树.当它被创建时,树具有订单2,1和0的子树.我们不能从订单0树中切除,但我们可以从订单2和订单1树中剪切单个子项.如果我们这样做,我们留下了一棵树,其中有三个孩子,一个是1号,2个是2号:
Smallest possible order 3 tree: *
/|\
* * *
|
*
现在我们可以发现一个模式.最小可能的顺序 - (n + 2)树将形成如下:首先创建一个正常的顺序(n + 2)树,其子节点为n + 1,n,n - 1,...,2 ,1,然后,通过切除它们的节点,使这些树尽可能小,而不从同一节点切割两个孩子.这会留下一个树,其子命令为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斐波那契数.
那为什么它被称为Fibonacci堆？ 因为n阶的每棵树必须至少有F n + 2个节点!
如果你很好奇,关于Fibonacci堆的原始论文中有这些最小树木的图片.看起来很漂亮!
希望这可以帮助!
我想给出一个直观的解释，我自己有一个“啊哈！” 时刻与。
树结构实现了 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) 时间的关键。当我们减少一个键时，如果新键仍然大于父键，那么我们不需要做任何其他事情，因为没有违反 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. 我们这里有一个斐波那契数列！
由于斐波那契数列是指数的，每棵树仍然保留指数数量的项目，因此为 EXTRACT-MIN 操作设法有 O(log n) 运行时间。但是请注意，DECREASE-KEY 现在只需要 O(1)。另一件很酷的事情是您可以将任何数字表示为斐波那契数的总和。例如，32 = 21 + 8 + 3 这意味着如果您需要在斐波那契堆中保存 32 个项目，您可以使用 3 棵树分别保存 21、8 和 3 个项目。然而，“合并”过程不会产生具有斐波那契节点数的树。它们仅在 DECREASE-KEY 或 DELETE 的这种更坏情况发生时发生。
进一步阅读
- 二项式堆- 斐波那契堆本质上是惰性二项式堆。这是一个很酷的数据结构，因为它展示了一种不同的方式，在树中存储指数项的高度而不是二叉堆。
- 斐波那契堆背后的直觉任何想要了解斐波那契堆核心的人都需要阅读。在这个主题上，教科书通常要么太浅，要么太杂乱，但这个 SO 答案的作者已经把它钉牢了。