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被定义为最大下界，使得每个可能的斐波那契堆中的每个 k 度子树都至少有 S _k个后代。