algorithm - 斐波那契堆 : Insertion, Extract-Min 和性能？

Question

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

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将始终为假，因此如果我们多次调用该函数，它永远不会给出准确的最小值。

• 如果此结构称为 Fibonacci“堆”，它在哪里维护堆属性？

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

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

Answer 1

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

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

关于你关于extract-min的问题，你的伪代码有错误。测试

x <> NIL

应该是

z <> NIL

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

至于如何维护堆属性:斐波那契堆中的每棵树都单独遵守堆属性。当调用 CONSOLIDATE 时，可以将多棵树合并回单独的树。这是维护堆属性的地方。将两棵树合并在一起时，斐波那契堆总是采用根值较大的树，并使其成为根值较小的树的根的子节点。这样，生成的树将遵循堆属性。

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

希望这对您有所帮助!