如何顯示具有n個節點的斐波納契堆可以有高度n？

Question

我想表明一個有n個節點的斐波那契堆可以有高度n。

我試過這個例子，但我不知道如何顯示這一般。

Answer 1

（我假設你的意思是高N - 1：高度n是不可能的，因爲有N個節點的最大高度是高度的鏈表N - 1）

前往高一個很簡單：加在三個節點，然後做一個dequeue-min。這消除了一個節點，並結合其他兩個節點，具有高度爲0，爲高度1的這種結構：

A 
| 
B 

如果再次重複這個過程，並確保新節點具有最低的優先級，你會得到一個兩個這樣的樹，這是再合併在一起，這樣的：

A 
|\ 
B C 
    | 
    D 

現在，做B.刪除操作這使得A和1階和標記：

A* 
| 
C 
| 
D 

重複此過程中再次（插入三個節點，都具有無限負的優先級，並調用出列分鐘）得到這個：

E 
|\ 
F A* 
    | 
    C 
    | 
    D 

刪除F到獲得

E* 
| 
A* 
| 
C 
| 
D 

如果多次執行的過程添加三個節點，刪除一個，然後刪除單個剩餘樹的單獨子節點，可以讓斐波那契堆爲任意n個高度爲n - 1的單個樹。

希望這會有所幫助！