爲什麼斐波納契堆需要級聯切割？

我正在從'算法介紹'學習f-heap，'減少鍵'操作真的讓我困惑 - 爲什麼這需要'級聯切割'？爲什麼斐波納契堆需要級聯切割？

如果該操作被移除：

補充堆（），插入（），最小（）和接頭（）的成本仍然明顯不變
提取-MIN（）是仍然是O （D（n）），因爲在O（n（H））'合併'操作中，大多數有根樹的成本可以在支付時支付，當它們被添加到根列表時，剩餘的成本O（D n））
遞減鍵（）：顯然O（1）

至於D（n），雖然我無法準確解釋它，但我認爲它仍然是O（lgn），因爲沒有'級聯切割'，節點可能只是稍後移動到根表 ，並且任何節點隱藏在其父下不影響效率。至少，這不會使情況變得更糟。

我的英文不好:(

任何人都可以幫忙嗎？感謝

來源

2013-04-11 exprosic

偉大的問題。將所有處於父母位置的信息扔掉似乎是非常不直觀的。 – 2014-06-14 14:45:28

的原因級聯切割是保持d（n）的低道歉。事實證明，如果允許任意數量的（n）可以增長爲線性，這使得刪除和刪除線性時間成爲線性時間。

直觀地說，您希望k階樹中的節點數爲這樣，你可以在統一的堆中只有對數多的樹，如果你可以裁減任意數量的節點從樹上，你失去了這個保證。具體來說，你可以拿一棵k階的樹，然後剪下所有的孫子。這會留下一棵樹，裏面有k個孩子，每個孩子都是樹葉。因此，您可以創建k階樹，其中只有k + 1個總節點。這意味着在最壞的情況下，你需要一棵n-1階的樹來保存所有的節點，所以D（n）變成n-1而不是O（log n）。

希望這會有所幫助！

來源

2013-04-11 07:07:34 templatetypedef

是的，你說得對。這種誤導性的D（n）的確會引起問題，但是當D（n）孩子的父母被提取時（這是我寫的原因在上面）時不會出現這種問題。當「合併」期間他們的父母選擇其父母**時出現** - 錯誤的D（）導致不平衡。現在考慮一下，如果在用cas-cut減少一個關鍵字之後，我可以保持所有的D（n），就像我的D切片一樣，也就是說，D（）可能小於兒童的數量 - 複雜度提取物分鐘仍然是O（lgn）。很難保持完全相同的D（），但我認爲還有另一種維持平衡的方式：每個節點都有一個S： – exprosic 2013-04-11 11:36:37

最初，它是節點的大小。顯然，它是2的二進制表示法的指數，10..000。當它的孩子被移除時，它的位數**（[log2（S）]）減少（1000-> 111,1011-> 101等），它將報告與其父代的差異。當差異大到足以減少父母的[log2（s）]時，差異會報告給祖父母，等等。 – exprosic 2013-04-11 11:37:12

同樣的一點是隱藏節點到父節點的減少，但是在O（1）時間內保持S（或D）與實際節點數量（具有S的樹至少有S/2個節點）之間的關係，並且在合併，使用S/D來保持平衡（結合具有相同D的節點或相同的[log2（S）]）。是對的嗎？ – exprosic 2013-04-11 11:37:38

爲什麼斐波納契堆需要級聯切割？

回答

相關問題