如何得到斐波那契堆的最壞情況

Question

什麼操作順序會給斐波那契堆造成最壞的情況？每個節點除了最後一個節點只有一個孩子？

例如：

5 
| 
6 
| 
7 
| 
8 

Answer 1

其實，這是最好的情況下（因爲你可以看到，提取敏總是容易的，因爲我們已經下令元素）。應該通過這種方式將反向排序元素序列（即，最小的元素將放在最後）得到它：

1. 插入兩個元素
2. 提取分鐘
3. 重複

Answer 2

我想jpalecek的答案不會產生請求的樹。這裏試試：

http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAnimation.html

此外，您可以只用插接件的任何數字達到同樣的結果，然後提取分鐘一次。無論如何，這不是要求。

達到你想要做到這一點的形式：

• 插入的任何元素的數量 - 比如說1到10
• 提取分鐘（現在你有一棵樹）
• 減少所有兒童-inf除最左邊以外，從最深處開始，從左到右（請參見下面的演示）。
• 每次減小後，刪除
• 重複步驟3

例如最小：

• 刀片1至10：

• 提取分鐘：

• 降低7到0：

• 提取分鐘：

• 降低5到0，提取分鐘，減少4到0，提取分鐘，減少3到0，提取分鐘，減少10到0，提取分鐘：

編輯：

我忘了有一個delete操作，使decrease然後extract min，所以你可以用它代替了下降然後提取分鐘我在上面做什麼。

，注意此時，當你有一個「單一路徑」樹，你可以輕鬆地被O的這個序列擴大它（1）操作：

• 將除最小較小的3個元素
• 提取分鐘
• 刪除新的右子

示範（繼續上次從例如步驟）：

• 插入1，0，-1：

• 提取分鐘：

• 刪除新的右子（1）：

所有圖像由this website