CLRS的斐波那契堆大小（x）分析有一個缺陷？

在CLRS的算法簡介第3版P.525中，當它分析大小（x）的下限時，我引用了一句話：「因爲將子節點添加到節點不能減小節點的大小， Sk以k單調遞增「。但事實上，我想我可以舉一個反例來說明Sk不一定會隨着k單調增加。在下面的圖中，密鑰= 1的節點的度數爲2，並且沒有度數爲2的其他節點，因此S2 = 8。類似地，S3 = 6。但是現在S3小於S2，這意味着Sk根本不隨k增加。CLRS的斐波那契堆大小（x）分析有一個缺陷？

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

通過執行一系列剪切和級聯剪切，可以從一個無序二項式子樹導出堆。

我想知道上述結構是否是一個有效的斐波那契堆。如果是這樣，那麼它也是一個有效的反例。

來源

2011-09-03 jscoot

你可能在這裏有更多的運氣：http://cstheory.stackexchange.com/ – alun

請說出什麼問題，即我現在沒有CLRS，所以我不能檢查問題陳述，我可以不明白你的意思是size（x），... –

size（x）是以x爲根的子樹中的節點總數。 – jscoot

小號_ķ被定義爲最大的下限，使得每個程度-K的子樹中每可能斐波那契堆具有至少新_ķ後代。

來源

2011-09-03 15:45:11 quaint

CLRS的斐波那契堆大小（x）分析有一個缺陷？

回答

相關問題