algorithm - 在斐波那契堆中实现合并

Question

Introduction to Algorithms 中的伪代码指出：

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

但是如何有效地实现每个根节点部分呢？原始根在整个合并过程中与其他相同程度的根相连，很难通过根节点的循环列表。如何确定是否检查了每个根节点？

Answer 1

您可以执行此操作的一种简单方法是使用三步过程：

1. 断开循环链接，使列表现在只是一个普通的双向链表。
2. 遍历双向链表并处理每棵树。这很棘手，因为正如您所提到的，每个节点上的 forward 和 next 指针可能会在迭代期间发生变化。
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;
}

希望这可以帮助！