CLRS 的斐波那契堆大小（x）分析有缺陷吗？
在CLRS的Introduction to Algorithms第3版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
可以通过执行一系列切割和级联切割从无序二项式子树派生堆。
我想知道上面的结构是否是有效的斐波那契堆。如果是这样，那么它也是一个有效的反例。
In CLRS's Introduction to Algorithms 3rd edition P.525, when it analyzes the size(x)'s lower bound, there is a sentence that I quote as "because adding children to a node cannot decrease the node’s size, the value of Sk increases monotonically with k". But in fact, i think i can give a counterexample to show that Sk does not necessarily increase monotonically with k. In the following graph, the degree of the node with key=1 is 2, and there is no other node with degree of 2. So S2=8. Similarly, S3=6. But now S3 is less than S2 which means Sk is not montonically increasing with k at all.
2 - 0 - 4 - 2 - 5 - 8 - 7 - 1
| / \
8 2 9
/ | \
10 14 16
| |
11 15
The heap can be derived from an unorder binomial subtree by executing a series of cuts and cascading-cuts.
I want to know whether the above structure is a valid fibonacci heap. If so, then it is also a valid counterexample.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
Sk 被定义为最大下界，使得每个可能的斐波那契堆中的每个 k 度子树都至少有 Sk 后代。
Sk is defined to be the greatest lower bound such that every degree-k subtree in every possible Fibonacci heap has at least Sk descendants.