1

我试图了解斐波那契堆，在堆中插入元素的伪代码是：

Fibonacci-Heap-Insert(H,x)
degree[x] := 0
p[x] := NIL
child[x] := NIL
left[x] := x
right[x] := x
mark[x] := FALSE
concatenate the root list containing x with root list H
if min[H] = NIL or key[x]<key[min[H]]
      then min[H] := x
n[H]:= n[H]+1

以下是我不明白的一些事情，

  • 什么是root list containing x以及如何将它与包含 H 的根列表连接起来？

在提取 min 时，我们执行以下操作：

    Fibonacci-Heap-Extract-Min(H)
     z:= min[H]
     if x <> NIL
         then for each child x of z
            do add x to the root list of H
                p[x]:= NIL
            remove z from the root list of H
            if z = right[z]
                then min[H]:=NIL
            else
                  min[H]:=right[z]
                  CONSOLIDATE(H)
            n[H] := n[H]-1
     return z

（这里是其他功能，合并和链接，http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAlgorithm.html）

  • 在前面的insert函数中，我们将x的child和p设置为nil，在提取min时，if <> nil总是为false，所以如果我们多次调用该函数，它永远不会给出准确的min。

  • 如果这个结构被称为斐波那契“堆”，它在哪里维护堆属性？

  • 如果我们在 Dijkstra 算法中使用二进制堆而不是斐波那契堆，所花费的时间会几乎与使用数组或链表一样慢吗？

谁能解释我遇到的困难？谢谢你。

4

1 回答 1

2

您在这里有很多问题，所以我会尽力回答所有问题。

对于您的第一个问题：斐波那契堆是作为一个树的集合实现的，所有这些树都以一个循环的双向链表链接在一起。当插入函数要求您将 x 与根列表 H 连接时，它要求您获取一个已创建的单例节点 (x) 并将其连接到所有现有树 H 的循环双向链表。

对于您关于 extract-min 的问题，您的伪代码中有错误。考试

x <> NIL

应该

z <> NIL

x 没有在函数中定义，所以这段代码不可能像写的那样工作。

至于如何维护堆属性：斐波那契堆中的每棵树都单独服从堆属性。调用 CONSOLIDATE 时，可以将多棵树重新合并为单独的树。这是维护堆属性的地方。当合并两棵树时，斐波那契堆总是取根值较大的树，并使其成为根值较小的树的根的子节点。这样，生成的树就服从堆属性。

最后，Dijkstra 和堆：具有基于堆的优先级队列的 Dijkstra 算法需要时间 O(m log n) 才能完成，而支持 Fibonacci-heap 的 Dijkstra 需要 O(m + n log n)，这对于稀疏图来说渐近更快. 然而，在实践中，斐波那契堆往往比二叉堆慢，因为隐藏在 big-O 项中的常数因子更高，这既是因为实现要复杂得多，也是因为它们的引用局部性更差。然而，Dijkstra 的二进制堆版本在理论上和实践上都比 Dijkstra 的链表或排序数组支持版本快得多。

希望这可以帮助！

于 2013-01-11T03:15:05.590 回答