_Algorithm Alley_ by John Boyer Figure 1: Input: Graph G, vertices S (start), T (terminate) Declare: H (initially empty heap) 1: For all vertices v 2: if v == S then v.cost := 0 3: else v.cost := infinity 3: Insert v into H 4: Repeat 5: M := ExtractMin(H) 6: For each vertex A attached to M 7: w := cost of edge from M to A 8: if (M.cost + w < A.cost) 9: Decrease A's Key to (M.cost + w) 10: A.backlink := M 11: Until M = T 12: Output T.cost 13: Output vertices on chain of backlinks from T to S Listing One //===================================================================== // ExtractMin() - O(n) worst-case actual; O(lg n) amortized //===================================================================== FibHeapNode *FibHeap::ExtractMin() { FibHeapNode *Result; FibHeap *ChildHeap = NULL; // Remove minimum node and set MinRoot to next node if ((Result = Minimum()) == NULL) return NULL; MinRoot = Result->Right; Result->Right->Left = Result->Left; Result->Left->Right = Result->Right; Result->Left = Result->Right = NULL; NumNodes --; if (Result->Mark) { NumMarkedNodes --; Result->Mark = 0; } Result->Degree = 0; // Attach child list of Minimum node to the root list of the heap // If there is no child list, then do no work if (Result->Child == NULL) { if (MinRoot == Result) MinRoot = NULL; } // If MinRoot==Result then there was only one root tree, so the root list is // the child list of that node (NULL if this is the last node in the list) else if (MinRoot == Result) MinRoot = Result->Child; // If MinRoot is different, then the child list is pushed into a new temporary // heap, which is then merged by Union() onto the root list of this heap. else { ChildHeap = new FibHeap(); ChildHeap->MinRoot = Result->Child; } // Complete the disassociation of the Result node from the heap if (Result->Child != NULL) Result->Child->Parent = NULL; Result->Child = Result->Parent = NULL; // If there was a child list, then we now merge it with rest of the root list if (ChildHeap) Union(ChildHeap); // Consolidate heap to find new minimum and do reorganize work if (MinRoot != NULL) _Consolidate(); // Return the minimum node, which is now disassociated with the heap // It has Left, Right, Parent, Child, Mark and Degree cleared. return Result; } //==================================================================== // Consolidate(). Internal function that reorganizes heap as part of an // ExtractMin(). We must find new minimum in heap, which could be anywhere // along the root list. The search could be O(n) since all nodes could be on // the root list. So, we reorganize the tree into more of a binomial forest // structure, and then find the new minimum on the consolidated O(lg n) sized // root list, and in the process set each Parent pointer to NULL, // and count the number of resulting subtrees. // After a list of n inserts, there will be n nodes on the root list, // so the first ExtractMin() will be O(n) regardless of whether or not we // consolidate. However, the consolidation causes subsequent ExtractMin() // operations to be O(lg n). Furthermore, the extra cost of the first // ExtractMin() is covered by the higher amortized cost of Insert(), which is // the real governing factor in how costly the first ExtractMin() will be. //===================================================================== void FibHeap::_Consolidate() { FibHeapNode *x, *y, *w; FibHeapNode *A[1+8*sizeof(long)]; // 1+lg(n) int I=0, Dn = 1+8*sizeof(long); short d; // Initialize the consolidation detection array for (I=0; I < Dn; I++) A[I] = NULL; // We need to loop through all elements on root list. When a collision of // degree is found, the two trees are consolidated in favor of the one with // the lesser element key value. We first need to break the circle so that we // can have a stopping condition (we can't go around until we reach the tree // we started with because all root trees are subject to becoming a child // during the consolidation). MinRoot->Left->Right = NULL; MinRoot->Left = NULL; w = MinRoot; do { x = w; d = x->Degree; w = w->Right; // We need another loop here because the consolidated result // may collide with another large tree on the root list. while (A[d] != NULL) { y = A[d]; if (*y < *x) _Exchange(x, y); if (w == y) w = y->Right; _Link(y, x); A[d] = NULL; d++; } A[d] = x; } while (w != NULL); // Now we rebuild the root list, find the new minimum, set all root list // nodes' parent pointers to NULL and count the number of subtrees. MinRoot = NULL; NumTrees = 0; for (I = 0; I < Dn; I++) if (A[I] != NULL) _AddToRootList(A[I]); } //===================================================================== void FibHeap::_AddToRootList(FibHeapNode *x) { if (x->Mark) NumMarkedNodes --; x->Mark = 0; NumNodes--; Insert(x); } //==== Node y is moved from the root list to become a subtree of node x. ==== void FibHeap::_Link(FibHeapNode *y, FibHeapNode *x) { // Remove node y from root list if (y->Right != NULL) y->Right->Left = y->Left; if (y->Left != NULL) y->Left->Right = y->Right; NumTrees--; // Make node y a singleton circular list with a parent of x y->Left = y->Right = y; y->Parent = x; // If node x has no children, then list y is its new child list if (x->Child == NULL) x->Child = y; // Otherwise, node y must be added to node x's child list else { y->Left = x->Child; y->Right = x->Child->Right; x->Child->Right = y; y->Right->Left = y; } // Increase the degree of node x because it's now a bigger tree x->Degree ++; // Node y has just been made a child, so clear its mark if (y->Mark) NumMarkedNodes--; y->Mark = 0; } Listing Two //===================================================================== // DecreaseKey() - O(lg n) actual; O(1) amortized // The O(lg n) actual cost stems from the fact that the depth, and // therefore the number of ancestor parents, is bounded by O(lg n). //===================================================================== int FibHeap::DecreaseKey(FibHeapNode *theNode, FibHeapNode& NewKey) { FibHeapNode *theParent; if (theNode==NULL || *theNode < NewKey) return NOTOK; *theNode = NewKey; theParent = theNode->Parent; if (theParent != NULL && *theNode < *theParent) { _Cut(theNode, theParent); _CascadingCut(theParent); } if (*theNode < *MinRoot) MinRoot = theNode; return OK; } //==== Remove node x from the child list of its parent node y ==== void FibHeap::_Cut(FibHeapNode *x, FibHeapNode *y) { if (y->Child == x) y->Child = x->Right; if (y->Child == x) y->Child = NULL; y->Degree --; x->Left->Right = x->Right; x->Right->Left = x->Left; _AddToRootList(x); } //===================================================================== // Cuts each node in parent list, putting successive ancestor nodes on the root // list until we either arrive at the root list or until we find an ancestor // that is unmarked. When a mark is set (which only happens during a cascading // cut), it means that one child subtree has been lost; if a second subtree is // lost later during another cascading cut, then we move the node to the root // list so that it can be re-balanced on the next consolidate. //===================================================================== void FibHeap::_CascadingCut(FibHeapNode *y) { FibHeapNode *z = y->Parent; while (z != NULL) { if (y->Mark == 0) { y->Mark = 1; NumMarkedNodes++; z = NULL; } else { _Cut(y, z); y = z; z = y->Parent; } } }