實現鞏固在斐波那契堆

Question

中的僞來自Introduction to Algorithms狀態：

for each node w in the root list of H 
    link trees of the same degree 

但如何高效地實現每個根節點一部分？在整合過程中，原始根與同一度的其他根相關聯，這使得僅通過根節點的循環列表就很困難。我怎樣才能決定我是否檢查過每個根節點？

Answer 1

一個簡單的方法，你可以做到這一點是使用三個步驟：

1. 中斷循環鏈接，這樣的名單現在只是一個普通的雙向鏈表。
2. 迭代雙鏈表並處理每棵樹。這很棘手，因爲正如你所提到的，在迭代過程中，每個節點上的前進和下一個指針可能會改變。
3. 關閉週期。

這裏是你可能會怎麼做每一個步驟：

中斷循環鏈接：

rootList->prev->next = NULL; 
rootList->prev = NULL; 

遍歷雙向鏈表。

Node* current = rootList; 
while (current != NULL) { 
    /* Cache the next node to visit so that even if the list changes, we can still 
    * remember where to go next. 
    */ 
    Node* next = current->next; 

    /* ... main Fibonacci heap logic ... */ 

    current = next; 
} 

修復的雙向鏈表：

Node* curr = rootList; 
if (curr != NULL) { // If list is empty, no processing necessary. 
    while (curr->next != NULL) { 
     curr = curr->next; 
    } 
    curr->next = rootList; 
    rootList->prev = curr; 
} 

希望這有助於！