algorithm - CLRS 的 Fibonacci Heap size(x) 分析有缺陷？

Question

在CLRS的Introduction to Algorithms 3rd edition P.525中，当它分析size(x)的下界时，有一句话我引用为“因为向节点添加子节点不能减小节点的大小，所以值Sk 随 k"单调增加。但实际上，我想我可以举一个反例来说明Sk不一定随k单调递增。在下图中，key=1的节点的度数为2，没有其他度数为2的节点。所以S2=8。同样，S3=6。但是现在 S3 小于 S2，这意味着 Sk 根本不随 k 单调增加。

2 - 0 - 4 - 2 - 5 - 8 - 7 -  1
            |               /  \
            8              2    9
                              / | \
                             10 14 16
                             |  |
                             11 15

可以通过执行一系列切割和级联切割从无序二项式子树派生堆。

我想知道上面的结构是否是一个有效的斐波那契堆。如果是这样，那么它也是一个有效的反例。

Answer 1

S_k 被定义为最大的下限，使得 every 可能的 Fibonacci 堆中的每个 k 度子树至少有 S_k 后代。