Implementing Consolidate in Fibonacci heap

Question

The pseudocode from Introduction to Algorithms states:

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

But how to efficiently implement the for each root node part? Original roots are linked to other roots of the same degree throughout the process of consolidation, which makes it difficult to just pass through the circular list of root nodes. How can I decide whether I have checked every root node or not?

Answer 1

One simple way that you could do this would be to use a three-step process:

1. Break the circular link so that the list is now just a normal doubly-linked list.
2. Iterate over the doubly-linked list and process each tree. This is tricky because, as you've mentioned, the forward and next pointers on each node might change during the iteration.
3. Close the cycle.

Here's how you might do each step:

Break the circular link:

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

Iterate over the doubly-linked list.

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

Repair the doubly-linked list:

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

Hope this helps!