00001 #ifdef HAVE_CONFIG_H 00002 #include <tumble-conf.h> 00003 #endif /* HAVE_CONFIG_H */ 00004 00005 00006 #define _FIBHEAP_CPP 00007 00008 //*************************************************************************** 00009 // This Fibonacci heap implementation is Copyright (c) 1996 by John Boyer. 00010 // See the header file for free usage information. 00011 //*************************************************************************** 00012 00013 //*************************************************************************** 00014 // The classes in this package are designed to allow the package user 00015 // to quickly and easily develop applications that require a heap data 00016 // structure. Using amortized analysis, the asymptotically fastest heap 00017 // data structure is the Fibonacci heap. The constants are a little 00018 // high so the real speed gain will not be seen until larger data sets 00019 // are required, but in most cases, if the data set is small, then the 00020 // run-time will be neglible anyway. 00021 // 00022 // To use this heap class you need do only two things. First, subclass 00023 // the FibHeapNode class to create the class of objects that you'd 00024 // like to store in a heap. Second, create an instance of the FibHeap 00025 // class, which can then be used to Insert(), ExtractMin(), etc., 00026 // instances of your FibHeapNode subclass. Notice that you don't need 00027 // to create a subclass of the FibHeap class. 00028 // 00029 // The application-specific data object that you'd like to store in a heap 00030 // will have a key value. In the class that you derive from FibHeapNode, 00031 // you will need to define the key structure then provide assignment (=), 00032 // equality (==) and less-than operators and a destructor. These functions 00033 // are declared virtual so that the code in the FibHeap class can compare, 00034 // assign and destroy your objects by calling on your code. 00035 // 00036 // The overloaded operators in your defined class MUST call functions in 00037 // the Fibonacci heap node class first. For assignment, the function 00038 // FHN_Assign() should be called before code that deals with the copy of 00039 // the key value. For comparison operators, the function FHN_Cmp() should 00040 // appear first. If it returns 0, then keys can be compared as normal. 00041 // The following indicates what the three most common operators must do 00042 // based on the return value of FHN_Cmp() 00043 // 00044 // For ==, if zero returned, then compare keys 00045 // if non-zero X returned, then return 0 00046 // For <, if zero returned, then compare keys 00047 // if non-zero X returned, then return X<0?1:0 00048 // For >, if zero returned, then compare keys 00049 // if non-zero X returned, then return X>0?1:0 00050 //*************************************************************************** 00051 00052 00053 #include <cstdlib> 00054 #include <iostream> 00055 #include <cstdio> 00056 #include "fibheap.h" 00057 00058 using namespace std; 00059 //*************************************************************************** 00060 //========================================================= 00061 // FibHeapNode Constructor 00062 //========================================================= 00063 //*************************************************************************** 00064 /* 00065 FibHeapNode::FibHeapNode() 00066 { 00067 Left = Right = Parent = Child = NULL; 00068 Degree = Mark = NegInfinityFlag = 0; 00069 } 00070 */ 00071 //========================================================= 00072 // FibHeapNode Destructor 00073 // 00074 // Body is empty, but declaration is required in order to 00075 // force virtual. This will ensure that FibHeap class 00076 // calls derived class destructors. 00077 //========================================================= 00078 00079 FibHeapNode::~FibHeapNode() 00080 { 00081 } 00082 00083 //========================================================= 00084 // FHN_Assign() 00085 // 00086 // To be used as first step of an assignment operator in a 00087 // derived class. The derived class will handle assignment 00088 // of key value, and this function handles copy of the 00089 // NegInfinityFlag (which overrides the key value if it is 00090 // set). 00091 //========================================================= 00092 /* 00093 void FibHeapNode::FHN_Assign(FibHeapNode& RHS) 00094 { 00095 NegInfinityFlag = RHS.NegInfinityFlag; 00096 } 00097 */ 00098 //========================================================= 00099 // FHN_Cmp() 00100 // 00101 // To be used as the first step of ALL comparators in a 00102 // derived class. 00103 // 00104 // Compares the relative state of the two neg. infinity 00105 // flags. Note that 'this' is the left hand side. If 00106 // LHS neg. infinity is set, then it will be less than (-1) 00107 // the RHS unless RHS neg. infinity flag is also set. 00108 // Only if function returns 0 should the key comparison 00109 // defined in the derived class be performed, e.g. 00110 // 00111 // For ==, if zero returned, then compare keys 00112 // if non-zero X returned, then return 0 00113 // For <, if zero returned, then compare keys 00114 // if non-zero X returned, then return X<0?1:0 00115 // For >, if zero returned, then compare keys 00116 // if non-zero X returned, then return X>0?1:0 00117 //========================================================= 00118 /* 00119 int FibHeapNode::FHN_Cmp(FibHeapNode& RHS) 00120 { 00121 if (NegInfinityFlag) 00122 return RHS.NegInfinityFlag ? 0 : -1; 00123 return RHS.NegInfinityFlag ? 1 : 0; 00124 } 00125 */ 00126 //======================================================================== 00127 // We do, on occasion, compare and assign objects of type FibHeapNode, but 00128 // only when the NegInfinityFlag is set. See for example FibHeap::Delete(). 00129 // 00130 // Also, these functions exemplify what a derived class should do. 00131 //======================================================================== 00132 00133 void FibHeapNode::operator =(FibHeapNode& RHS) 00134 { 00135 FHN_Assign(RHS); 00136 // Key assignment goes here in derived classes 00137 } 00138 00139 int FibHeapNode::operator ==(FibHeapNode& RHS) 00140 { 00141 if (FHN_Cmp(RHS)) return 0; 00142 // Key compare goes here in derived classes 00143 return 1; 00144 } 00145 00146 int FibHeapNode::operator <(FibHeapNode& RHS) 00147 { 00148 int X; 00149 00150 if ((X=FHN_Cmp(RHS)) != 0) 00151 return X < 0 ? 1 : 0; 00152 // Key compare goes here in derived classes 00153 return 0; 00154 } 00155 00156 //========================================================= 00157 // Print() 00158 //========================================================= 00159 00160 void FibHeapNode::Print() 00161 { 00162 if (NegInfinityFlag) 00163 cout << "-inf."; 00164 } 00165 00166 //*************************************************************************** 00167 //=========================================================================== 00168 // FibHeap Constructor 00169 //=========================================================================== 00170 //*************************************************************************** 00171 00172 FibHeap::FibHeap() 00173 { 00174 MinRoot = NULL; 00175 NumNodes = NumTrees = NumMarkedNodes = 0; 00176 ClearHeapOwnership(); 00177 } 00178 00179 //=========================================================================== 00180 // FibHeap Destructor 00181 //=========================================================================== 00182 00183 FibHeap::~FibHeap() 00184 { 00185 FibHeapNode *Temp; 00186 00187 if (GetHeapOwnership()) 00188 { 00189 while (MinRoot != NULL) 00190 { 00191 Temp = ExtractMin(); 00192 delete Temp; 00193 } 00194 } 00195 } 00196 00197 //=========================================================================== 00198 // Insert() - O(1) actual; O(2) amortized 00199 // 00200 // I am using O(2) here to indicate that although Insert() is 00201 // constant time, its amortized rating is more costly because some 00202 // of the work of inserting is done by other operations such as 00203 // ExtractMin(), which is where tree-balancing occurs. 00204 // 00205 // The child pointer is deliberately not set to NULL because Insert() 00206 // is also used internally to help put whole trees onto the root list. 00207 //=========================================================================== 00208 00209 void FibHeap::Insert(FibHeapNode *NewNode) 00210 { 00211 if (NewNode == NULL) return; 00212 00213 // If the heap is currently empty, then new node becomes singleton 00214 // circular root list 00215 00216 if (MinRoot == NULL) 00217 MinRoot = NewNode->Left = NewNode->Right = NewNode; 00218 00219 else 00220 { 00221 // Pointers from NewNode set to insert between MinRoot and MinRoot->Right 00222 00223 NewNode->Right = MinRoot->Right; 00224 NewNode->Left = MinRoot; 00225 00226 // Set Pointers to NewNode 00227 00228 NewNode->Left->Right = NewNode; 00229 NewNode->Right->Left = NewNode; 00230 00231 // The new node becomes new MinRoot if it is less than current MinRoot 00232 00233 if (*NewNode < *MinRoot) 00234 MinRoot = NewNode; 00235 } 00236 00237 // We have one more node in the heap, and it is a tree on the root list 00238 00239 NumNodes++; 00240 00241 NumTrees++; 00242 NewNode->Parent = NULL; 00243 } 00244 00245 //=========================================================================== 00246 // Union() - O(1) actual; O(1) amortized 00247 //=========================================================================== 00248 00249 void FibHeap::Union(FibHeap *OtherHeap) 00250 { 00251 FibHeapNode *Min1, *Min2, *Next1, *Next2; 00252 00253 if (OtherHeap == NULL || OtherHeap->MinRoot == NULL) return; 00254 00255 // We join the two circular lists by cutting each list between its 00256 // min node and the node after the min. This code just pulls those 00257 // nodes into temporary variables so we don't get lost as changes 00258 // are made. 00259 00260 Min1 = MinRoot; 00261 Min2 = OtherHeap->MinRoot; 00262 Next1 = Min1->Right; 00263 Next2 = Min2->Right; 00264 00265 // To join the two circles, we join the minimum nodes to the next 00266 // nodes on the opposite chains. Conceptually, it looks like the way 00267 // two bubbles join to form one larger bubble. They meet at one point 00268 // of contact, then expand out to make the bigger circle. 00269 00270 Min1->Right = Next2; 00271 Next2->Left = Min1; 00272 Min2->Right = Next1; 00273 Next1->Left = Min2; 00274 00275 // Choose the new minimum for the heap 00276 00277 if (*Min2 < *Min1) 00278 MinRoot = Min2; 00279 00280 // Set the amortized analysis statistics and size of the new heap 00281 00282 NumNodes += OtherHeap->NumNodes; 00283 NumMarkedNodes += OtherHeap->NumMarkedNodes; 00284 NumTrees += OtherHeap->NumTrees; 00285 00286 // Complete the union by setting the other heap to emptiness 00287 // then destroying it 00288 00289 OtherHeap->MinRoot = NULL; 00290 OtherHeap->NumNodes = 00291 OtherHeap->NumTrees = 00292 OtherHeap->NumMarkedNodes = 0; 00293 00294 delete OtherHeap; 00295 } 00296 00297 //=========================================================================== 00298 // Minimum - O(1) actual; O(1) amortized 00299 //=========================================================================== 00300 /* 00301 FibHeapNode *FibHeap::Minimum() 00302 { 00303 return MinRoot; 00304 } 00305 */ 00306 //=========================================================================== 00307 // ExtractMin() - O(n) worst-case actual; O(lg n) amortized 00308 //=========================================================================== 00309 00310 FibHeapNode *FibHeap::ExtractMin() 00311 { 00312 FibHeapNode *Result; 00313 FibHeap *ChildHeap = NULL; 00314 00315 // Remove minimum node and set MinRoot to next node 00316 00317 if ((Result = Minimum()) == NULL) 00318 return NULL; 00319 00320 MinRoot = Result->Right; 00321 Result->Right->Left = Result->Left; 00322 Result->Left->Right = Result->Right; 00323 Result->Left = Result->Right = NULL; 00324 00325 NumNodes --; 00326 if (Result->Mark) 00327 { 00328 NumMarkedNodes --; 00329 Result->Mark = 0; 00330 } 00331 Result->Degree = 0; 00332 00333 // Attach child list of Minimum node to the root list of the heap 00334 // If there is no child list, then do no work 00335 00336 if (Result->Child == NULL) 00337 { 00338 if (MinRoot == Result) 00339 MinRoot = NULL; 00340 } 00341 00342 // If MinRoot==Result then there was only one root tree, so the 00343 // root list is simply the child list of that node (which is 00344 // NULL if this is the last node in the list) 00345 00346 else if (MinRoot == Result) 00347 MinRoot = Result->Child; 00348 00349 // If MinRoot is different, then the child list is pushed into a 00350 // new temporary heap, which is then merged by Union() onto the 00351 // root list of this heap. 00352 00353 else 00354 { 00355 ChildHeap = new FibHeap(); 00356 ChildHeap->MinRoot = Result->Child; 00357 } 00358 00359 // Complete the disassociation of the Result node from the heap 00360 00361 if (Result->Child != NULL) 00362 Result->Child->Parent = NULL; 00363 Result->Child = Result->Parent = NULL; 00364 00365 // If there was a child list, then we now merge it with the 00366 // rest of the root list 00367 00368 if (ChildHeap) 00369 Union(ChildHeap); 00370 00371 // Consolidate heap to find new minimum and do reorganize work 00372 00373 if (MinRoot != NULL) 00374 _Consolidate(); 00375 00376 // Return the minimum node, which is now disassociated with the heap 00377 // It has Left, Right, Parent, Child, Mark and Degree cleared. 00378 00379 return Result; 00380 } 00381 00382 //=========================================================================== 00383 // DecreaseKey() - O(lg n) actual; O(1) amortized 00384 // 00385 // The O(lg n) actual cost stems from the fact that the depth, and 00386 // therefore the number of ancestor parents, is bounded by O(lg n). 00387 //=========================================================================== 00388 00389 int FibHeap::DecreaseKey(FibHeapNode *theNode, FibHeapNode& NewKey) 00390 { 00391 FibHeapNode *theParent; 00392 00393 if (theNode==NULL || *theNode < NewKey) 00394 return NOTOK; 00395 00396 *theNode = NewKey; 00397 00398 theParent = theNode->Parent; 00399 if (theParent != NULL && *theNode < *theParent) 00400 { 00401 _Cut(theNode, theParent); 00402 _CascadingCut(theParent); 00403 } 00404 00405 if (*theNode < *MinRoot) 00406 MinRoot = theNode; 00407 00408 return OK; 00409 } 00410 00411 //=========================================================================== 00412 // Delete() - O(lg n) amortized; ExtractMin() dominates 00413 // 00414 // Notice that if we don't own the heap nodes, then we clear the 00415 // NegInfinityFlag on the deleted node. Presumably, the programmer 00416 // will be reusing the node. 00417 //=========================================================================== 00418 00419 int FibHeap::Delete(FibHeapNode *theNode) 00420 { 00421 FibHeapNode Temp; 00422 int Result; 00423 00424 if (theNode == NULL) return NOTOK; 00425 00426 Temp.NegInfinityFlag = 1; 00427 Result = DecreaseKey(theNode, Temp); 00428 00429 if (Result == OK) 00430 if (ExtractMin() == NULL) 00431 Result = NOTOK; 00432 00433 if (Result == OK) 00434 { 00435 if (GetHeapOwnership()) 00436 delete theNode; 00437 else theNode->NegInfinityFlag = 0; 00438 } 00439 00440 return Result; 00441 } 00442 00443 //======================================================================== 00444 // Print() 00445 // 00446 // Used internally for debugging purposes. The function prints the key 00447 // value for each node along the root list, then it calls itself on each 00448 // child list. 00449 //======================================================================== 00450 00451 void FibHeap::Print(FibHeapNode *Tree, FibHeapNode *theParent) 00452 { 00453 FibHeapNode* Temp = NULL; 00454 00455 if (Tree == NULL) Tree = MinRoot; 00456 00457 Temp = Tree; 00458 do { 00459 if (Temp->Left == NULL) 00460 cout << "(Left is NULL)"; 00461 Temp->Print(); 00462 if (Temp->Parent != theParent) 00463 cout << "(Parent is incorrect)"; 00464 if (Temp->Right == NULL) 00465 cout << "(Right is NULL)"; 00466 else if (Temp->Right->Left != Temp) 00467 cout << "(Error in left link left) ->"; 00468 else cout << " <-> "; 00469 00470 Temp = Temp->Right; 00471 /* 00472 if (kbhit() && getch() == 27) 00473 { 00474 cout << "Hit a key to resume or ESC to break\n"; 00475 if (getch() == 27) 00476 break; 00477 } 00478 */ 00479 } while (Temp != NULL && Temp != Tree); 00480 cout << '\n'; 00481 00482 Temp = Tree; 00483 do { 00484 cout << "Children of "; 00485 Temp->Print(); 00486 cout << ": "; 00487 if (Temp->Child == NULL) 00488 cout << "NONE\n"; 00489 else Print(Temp->Child, Temp); 00490 Temp = Temp->Right; 00491 } while (Temp!=NULL && Temp != Tree); 00492 00493 if (theParent == NULL) 00494 { 00495 char ch; 00496 00497 cout << "Done Printing. Hit a key.\n"; 00498 cin >> ch; 00499 } 00500 } 00501 00502 //=========================================================================== 00503 //=========================================================================== 00504 /* 00505 void FibHeap::_Exchange(FibHeapNode*& N1, FibHeapNode*& N2) 00506 { 00507 FibHeapNode *Temp; 00508 00509 Temp = N1; 00510 N1 = N2; 00511 N2 = Temp; 00512 } 00513 */ 00514 //=========================================================================== 00515 // Consolidate() 00516 // 00517 // Internal function that reorganizes heap as part of an ExtractMin(). 00518 // We must find new minimum in heap, which could be anywhere along the 00519 // root list. The search could be O(n) since all nodes could be on 00520 // the root list. So, we reorganize the tree into more of a binomial forest 00521 // structure, and then find the new minimum on the consolidated O(lg n) sized 00522 // root list, and in the process set each Parent pointer to NULL, and count 00523 // the number of resulting subtrees. 00524 // 00525 // Note that after a list of n inserts, there will be n nodes on the root 00526 // list, so the first ExtractMin() will be O(n) regardless of whether or 00527 // not we consolidate. However, the consolidation causes subsequent 00528 // ExtractMin() operations to be O(lg n). Furthermore, the extra cost of 00529 // the first ExtractMin() is covered by the higher amortized cost of 00530 // Insert(), which is the real governing factor in how costly the first 00531 // ExtractMin() will be. 00532 //=========================================================================== 00533 00534 void FibHeap::_Consolidate() 00535 { 00536 FibHeapNode *x, *y, *w; 00537 FibHeapNode *A[1+8*sizeof(long)]; // 1+lg(n) 00538 int I=0, Dn = 1+8*sizeof(long); 00539 short d; 00540 00541 // Initialize the consolidation detection array 00542 00543 for (I=0; I < Dn; I++) 00544 A[I] = NULL; 00545 00546 // We need to loop through all elements on root list. 00547 // When a collision of degree is found, the two trees 00548 // are consolidated in favor of the one with the lesser 00549 // element key value. We first need to break the circle 00550 // so that we can have a stopping condition (we can't go 00551 // around until we reach the tree we started with 00552 // because all root trees are subject to becoming a 00553 // child during the consolidation). 00554 00555 MinRoot->Left->Right = NULL; 00556 MinRoot->Left = NULL; 00557 w = MinRoot; 00558 00559 do { 00560 //cout << "Top of Consolidate's loop\n"; 00561 //Print(w); 00562 00563 x = w; 00564 d = x->Degree; 00565 w = w->Right; 00566 00567 // We need another loop here because the consolidated result 00568 // may collide with another large tree on the root list. 00569 00570 while (A[d] != NULL) 00571 { 00572 y = A[d]; 00573 if (*y < *x) 00574 _Exchange(x, y); 00575 if (w == y) w = y->Right; 00576 _Link(y, x); 00577 A[d] = NULL; 00578 d++; 00579 //cout << "After a round of Linking\n"; 00580 //Print(x); 00581 } 00582 A[d] = x; 00583 00584 } while (w != NULL); 00585 00586 // Now we rebuild the root list, find the new minimum, 00587 // set all root list nodes' parent pointers to NULL and 00588 // count the number of subtrees. 00589 00590 MinRoot = NULL; 00591 NumTrees = 0; 00592 for (I = 0; I < Dn; I++) 00593 if (A[I] != NULL) 00594 _AddToRootList(A[I]); 00595 } 00596 00597 //=========================================================================== 00598 // The node y is removed from the root list and becomes a subtree of node x. 00599 //=========================================================================== 00600 00601 void FibHeap::_Link(FibHeapNode *y, FibHeapNode *x) 00602 { 00603 // Remove node y from root list 00604 00605 if (y->Right != NULL) 00606 y->Right->Left = y->Left; 00607 if (y->Left != NULL) 00608 y->Left->Right = y->Right; 00609 NumTrees--; 00610 00611 // Make node y a singleton circular list with a parent of x 00612 00613 y->Left = y->Right = y; 00614 y->Parent = x; 00615 00616 // If node x has no children, then list y is its new child list 00617 00618 if (x->Child == NULL) 00619 x->Child = y; 00620 00621 // Otherwise, node y must be added to node x's child list 00622 00623 else 00624 { 00625 y->Left = x->Child; 00626 y->Right = x->Child->Right; 00627 x->Child->Right = y; 00628 y->Right->Left = y; 00629 } 00630 00631 // Increase the degree of node x because it's now a bigger tree 00632 00633 x->Degree ++; 00634 00635 // Node y has just been made a child, so clear its mark 00636 00637 if (y->Mark) NumMarkedNodes--; 00638 y->Mark = 0; 00639 } 00640 00641 //=========================================================================== 00642 //=========================================================================== 00643 00644 void FibHeap::_AddToRootList(FibHeapNode *x) 00645 { 00646 if (x->Mark) NumMarkedNodes --; 00647 x->Mark = 0; 00648 00649 NumNodes--; 00650 Insert(x); 00651 } 00652 00653 //=========================================================================== 00654 // Remove node x from the child list of its parent node y 00655 //=========================================================================== 00656 00657 void FibHeap::_Cut(FibHeapNode *x, FibHeapNode *y) 00658 { 00659 if (y->Child == x) 00660 y->Child = x->Right; 00661 if (y->Child == x) 00662 y->Child = NULL; 00663 00664 y->Degree --; 00665 00666 x->Left->Right = x->Right; 00667 x->Right->Left = x->Left; 00668 00669 _AddToRootList(x); 00670 } 00671 00672 //=========================================================================== 00673 // Cuts each node in parent list, putting successive ancestor nodes on the 00674 // root list until we either arrive at the root list or until we find an 00675 // ancestor that is unmarked. When a mark is set (which only happens during 00676 // a cascading cut), it means that one child subtree has been lost; if a 00677 // second subtree is lost later during another cascading cut, then we move 00678 // the node to the root list so that it can be re-balanced on the next 00679 // consolidate. 00680 //=========================================================================== 00681 00682 void FibHeap::_CascadingCut(FibHeapNode *y) 00683 { 00684 FibHeapNode *z = y->Parent; 00685 00686 while (z != NULL) 00687 { 00688 if (y->Mark == 0) 00689 { 00690 y->Mark = 1; 00691 NumMarkedNodes++; 00692 z = NULL; 00693 } 00694 else 00695 { 00696 _Cut(y, z); 00697 y = z; 00698 z = y->Parent; 00699 } 00700 } 00701 } 00702