data-structures - 斐波那契堆中的 dequeuemin

Question

我想问一下斐波那契堆。如果我有这种情况：

A
|
B

然后，我们再添加两个节点 C 和 D：

A
|\
B C
  |
  D

现在我们删除 B：

A
|
C
|
D

现在我们添加 E 和 F。

我看到它创建了一棵这样的树：

E
|\
F A
  |
  C
  |
  D

但我不明白为什么 E 和 F 与树相连。根据我的阅读，我们连接具有相同等级的树（例如，一个节点的树与另一个节点的树），我错了吗？

非常感谢。

Answer 1

如果您将节点 C 和 D 添加到第一个斐波那契堆中，您将不会得到您绘制的树。相反，你会有这个堆：

    A   C   D
    |
    B

请记住，斐波那契堆懒惰地将每个新添加的值添加到树的顶级列表中，并且仅在删除时合并事物。如果要删除 B，则将其提升到顶层，如下所示：

    A   B   C   D

然后，您将删除 B：

    A   C   D

现在，您将扫描根列表并将相同顺序的树合并在一起。假设您按 A、C、D 的顺序扫描节点。首先，您将 A 和 C 合并在一起，如下所示：

   A   D
   |
   C

此时，不会发生进一步的合并，因为每个订单只有一棵树。

如果然后添加 E 和 F，您会将它们放在顶层，如下所示：

   A   D   E   F
   |
   C

所以是的，你是对的，这些节点不应该被添加到树中。