为什么斐波那契堆被称为斐波那契堆？ [英] Why is a Fibonacci heap called a Fibonacci heap?
问题描述
斐波那契堆数据结构的名称中包含斐波纳契，但数据结构中似乎没有使用斐波纳契数字。根据维基百科的文章：
The Fibonacci heap data structure has the word "Fibonacci" in its name, but nothing in the data structure seems to use Fibonacci numbers. According to the Wikipedia article:
斐波纳契堆的名字来自运行时分析中使用的斐波那契数字。
The name of Fibonacci heap comes from Fibonacci numbers which are used in the running time analysis.
斐波纳契堆中是如何出现斐波那契数的？
How do these Fibonacci numbers arise in the Fibonacci heap?
推荐答案
斐波那契堆由一系列不同秩序的较小的堆序树构成，这些树遵从某些结构约束。斐波纳契序列的出现是因为这些树以这样的方式构造，使得阶数n的树在其中具有至少F n + 2个节点，其中F n + 2 是为了了解为什么这个结果是真的，让我们先来看看如何构建斐波那契堆中的树，那么第（n + 2）个斐波纳契数字。
The Fibonacci heap is made up of a collection of smaller heap-ordered trees of different "orders" that obey certain structural constraints. The Fibonacci sequence arises because these trees are constructed in a way such that a tree of order n has at least Fn+2 nodes in it, where Fn+2 is the (n + 2)nd Fibonacci number.
最初，无论何时将节点放入Fibonacci堆中，它将被放入一个包含该节点的0的树中。每当Fibonacci堆中的值被删除时，斐波纳契堆中的一些树结合在一起，使得树的数量不会变得太大。
To see why this result is true, let's begin by seeing how the trees in the Fibonacci heap are constructed. Initially, whenever a node is put into a Fibonacci heap, it is put into a tree of order 0 that contains just that node. Whenever a value is removed from the Fibonacci heap, some of the trees in the Fibonacci heap are coalesced together such that the number of trees doesn't grow too large.
当将树木结合在一起，斐波纳契堆只将相同顺序的树木结合在一起。要将n个阶n的树结合到一个n + 1的树中，斐波纳契堆取两个树中的任一个比另一个树更大的根值，然后使该树成为另一棵树的一个小孩。这个事实的一个后果是，秩序n的树总是具有n个孩子。
When combining trees together, the Fibonacci heap only combines together trees of the same order. To combine two trees of order n into a tree of order n + 1, the Fibonacci heap takes whichever of the two trees has a greater root value than the other, then makes that tree a child of the other tree. One consequence of this fact is that trees of order n always have exactly n children.
斐波纳契堆的主要吸引力是它支持有效减少关键字（以摊余O（1））表示。为了支持这一点，斐波那契堆实现减少键如下：减少存储在某个节点中的值的键，该节点从其父树切割并被视为其自己的单独的树。当这种情况发生时，它的旧父节点的顺序减少一个。例如，如果一个订单4树中有一个从它剪切的小孩，它会缩小到一个3号树，这是有道理的，因为一棵树的顺序应该是它包含的子代数。
The main attraction of the Fibonacci heap is that it supports the decrease-key efficiently (in amortized O(1)). In order to support this, the Fibonacci heap implements decrease-key as follows: to decrease the key of a value stored in some node, that node is cut from its parent tree and treated as its own separate tree. When this happens, the order of its old parent node is decreased by one. For example, if an order 4 tree has a child cut from it, it shrinks to an order 3 tree, which makes sense because the order of a tree is supposed to be the number of children it contains.
这样做的问题是，如果从同一棵树中切断太多的树，我们可能会有一个大订单的树，但是包含很少的节点。斐波纳契堆的时间保证只有在具有大量订单的树包含大量节点的情况下才可能，如果我们可以从树中切割我们想要的任何节点，我们可以轻松地进入一个大订单树的情况为了解决这个问题，斐波纳契堆需要一个要求 - 如果你从一棵树上剪下两个孩子，你必须依次进行操作。
The problem with doing this is that if too many trees get cut off from the same tree, we might have a tree with a large order but which contains a very small number of nodes. The time guarantees of a Fibonacci heap are only possible if trees with large orders contain a huge number of nodes, and if we can just cut any nodes we'd like from trees we could easily get into a situation where a tree with a huge order only contains a small number of nodes.
从父母中切下那棵树。这意味着形成斐波纳契堆的树不会被减少键太严重损坏。
To address this, Fibonacci heaps make one requirement - if you cut two children from a tree, you have to in turn cut that tree from its parent. This means that the trees that form a Fibonacci heap won't be too badly damaged by decrease-key.
现在我们可以得到关于斐波纳契数字的部分。在这一点上，我们可以在斐波纳契堆中说出以下几点：
And now we can get to the part about Fibonacci numbers. At this point, we can say the following about the trees in a Fibonacci heap:
- / li>
- 订单n是通过采取两个订单n - 1的树和一个另一个孩子组成的。
- 如果一棵树丢了两个孩子那棵树从它的父母被切掉了。
所以现在我们可以问 - 你可以做的最小的树是什么这些假设？
So now we can ask - what are the smallest possible trees that you can make under these assumptions?
我们来试试一些例子。只有一个可能的订单树0，它只是一个单一的节点：
Let's try out some examples. There is only one possible tree of order 0, which is a just a single node:
Smallest possible order 0 tree: *
订单1中最小的树必须至少是一个带有子节点的节点。我们可以做的最小的孩子是一个单个节点，最小的order-0树作为一个孩子，这是这个树：
The smallest possible tree of order 1 would have to be at least a node with a child. The smallest possible child we could make is a single node with the smallest order-0 tree as a child, which is this tree:
Smallest possible order 1 tree: *
|
*
订单2的最小树怎么样？这是事情变得有趣的地方。这棵树当然必须有两个孩子，它将通过将2个树木合并在一起而形成。因此，树最初将有两个孩子 - 一棵树为0，一棵树为1，但请记住 - 我们可以合并后将孩子从树上切下来！在这种情况下，如果我们切断了1号树的孩子，我们将留下一棵有两个孩子的树，两棵树都是0的树：
What about the smallest tree of order 2? This is where things get interesting. This tree certainly has to have two children, and it would be formed by merging together two trees of order 1. Consequently, the tree would initially have two children - a tree of order 0 and a tree of order 1. But remember - we can cut away children from trees after merging them! In this case, if we cut away the child of the tree of order 1, we would be left with a tree with two children, both of which are trees of order 0:
Smallest possible order 2 tree: *
/ \
* *
订单3如何？像以前一样，这棵树将通过将2个树结合在一起来完成。然后，我们尝试尽可能多地删除这个3号树的子树。当它创建时，树具有2，1和0的顺序子树。我们不能从0树中删除，但是我们可以从顺序2和顺序1树中切割一个单独的子节点。如果我们这样做，我们会留下一个树，里面有三个孩子，一个是1号，另一个是2号：
How about order 3? As before, this tree would be made by merging together two trees of order 2. We would then try to cut away as much of the subtrees of this order-3 tree as possible. When it's created, the tree has subtrees of orders 2, 1, and 0. We can't cut away from the order 0 tree, but we can cut a single child from the order 2 and order 1 tree. If we do this, we're left with a tree with three children, one of order 1, and two of order 2:
Smallest possible order 3 tree: *
/|\
* * *
|
*
现在我们可以发现一个模式。最小可能的顺序 - （n + 2）树将形成如下：首先创建一个正常的顺序（n + 2）树，它具有n + 1，n，n - 1，...， ，1，然后，通过从节点中切断节点，使这些树尽可能小，而不会从同一节点切割两个孩子。这个树与一个有n，n - 2，...，1，0和0的小孩的树。
Now we can spot a pattern. The smallest possible order-(n + 2) tree would be formed as follows: start by creating a normal order (n + 2) tree, which has children of orders n + 1, n, n - 1, ..., 2, 1, 0. Then, make those trees as small as possible by cutting away nodes from them without cutting two children from the same node. This leaves a tree with children of orders n, n - 2, ..., 1, 0, and 0.
现在我们可以写一个递归关系来尝试确定这些树中有多少个节点。如果我们这样做，我们得到以下内容，其中NC（n）代表可能在n阶树中的最小节点数目：
We can now write a recurrence relation to try to determine how many nodes are in these trees. If we do this, we get the following, where NC(n) represents the smallest number of nodes that could be in a tree of order n:
NC(0) = 1
NC(1) = 2
NC(n + 2) = NC(n) + NC(n - 1) + ... + NC(1) + NC(0) + NC(0) + 1
对于根节点本身。
如果我们扩展这些术语，我们得到以下内容：
If we expand out these terms, we get the following:
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 + 2个节点，其中F n + 2< n + 2>是第（n + 2）个斐波那契数。
If you'll notice, this is exactly the Fibonacci series offset by two positions. In other words, each of these trees has to have at least Fn+2 nodes in them, where Fn + 2 is the (n + 2)nd Fibonacci number.
那么为什么它叫做斐波纳契堆？ 因为每个树的树都必须至少有F + n + 2个子节点！
So why is it called a Fibonacci heap? Because each tree of order n has to have at least Fn+2 nodes in it!
如果你好奇， 原始论文在斐波纳契堆积 有这些尽可能小的树的图片。看到很漂亮！
If you're curious, the original paper on Fibonacci heaps has pictures of these smallest possible trees. It's pretty nifty to see!
希望这有帮助！
这篇关于为什么斐波那契堆被称为斐波那契堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
