algorithm - 在 Fibonacci 堆中实现 Consolidate

Question

伪代码来自 Introduction to Algorithms 指出:

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

但是如何高效地实现for each root node部分呢？原始根在整个合并过程中都与同级的其他根相连，这使得仅通过根节点的循环列表变得困难。我如何确定我是否检查了每个根节点？

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;
}

希望这对您有所帮助!