00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035 #ifndef _FIBHEAP_H_
00036 #define _FIBHEAP_H_
00037
00038
00039 #include "chomp/struct/multitab.h"
00040
00041
00042
00043 namespace chomp {
00044 namespace homology {
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 template <class element>
00063 class FibonacciHeap
00064 {
00065 public:
00066
00067 typedef int NodePtr;
00068
00069
00070 static const int NullPtr = -1;
00071
00072 private:
00073
00074
00075 struct Node
00076 {
00077
00078
00079 element key;
00080
00081
00082
00083
00084 bool mark;
00085
00086
00087
00088
00089 int degree;
00090
00091
00092 int number;
00093
00094
00095 NodePtr parent;
00096
00097
00098 NodePtr child;
00099
00100
00101 NodePtr left;
00102
00103
00104 NodePtr right;
00105 };
00106
00107 public:
00108
00109
00110 FibonacciHeap (int maxSize = 0);
00111
00112
00113 ~FibonacciHeap ();
00114
00115
00116
00117
00118
00119 int Insert (const element &value);
00120
00121
00122
00123 int Minimum () const;
00124
00125
00126 const element &Value (int number) const;
00127
00128
00129
00130
00131
00132
00133
00134
00135
00136
00137 element ExtractMinimum ();
00138
00139
00140
00141 void DecreaseKey (int number, const element &value);
00142
00143
00144 void Delete (int number);
00145
00146 private:
00147
00148 FibonacciHeap (const FibonacciHeap<element> &);
00149
00150
00151 FibonacciHeap<element> &operator = (const FibonacciHeap<element> &);
00152
00153
00154 NodePtr minRoot;
00155
00156
00157
00158 int nodeCount;
00159
00160
00161
00162
00163
00164
00165 multitable<Node> nodes;
00166
00167
00168
00169
00170
00171 element minValue;
00172
00173
00174
00175
00176
00177
00178
00179
00180 void Consolidate ();
00181
00182
00183 multitable<NodePtr> auxArray;
00184
00185
00186 int arrayPrepared;
00187
00188
00189 void Cut (const typename FibonacciHeap<element>::NodePtr &x,
00190 const typename FibonacciHeap<element>::NodePtr &y);
00191
00192
00193 void CascadingCut (typename FibonacciHeap<element>::NodePtr y);
00194
00195
00196 void showGraph (std::ostream &out, int depth,
00197 const typename FibonacciHeap<element>::NodePtr &x) const;
00198
00199 public:
00200
00201
00202 friend inline std::ostream &operator << (std::ostream &out,
00203 const FibonacciHeap<element> &h)
00204 {
00205 out << "Fibonacci heap (min root = " << h. minRoot << "):\n";
00206 NodePtr rootPtr = h. minRoot;
00207 if (rootPtr == NullPtr)
00208 return out;
00209 do
00210 {
00211 h. showGraph (out, 0, rootPtr);
00212 rootPtr = h. nodes [rootPtr]. right;
00213 } while (rootPtr != h. minRoot);
00214 return out;
00215 }
00216
00217 };
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227 template <class element>
00228 void FibonacciHeap<element>::showGraph (std::ostream &out, int depth,
00229 const typename FibonacciHeap<element>::NodePtr &x) const
00230 {
00231
00232 for (int i = 0; i < depth; ++ i)
00233 out << "| ";
00234 out << "+-- [" << nodes [x]. number << ": " << nodes [x]. key << "]";
00235 if (nodes [x]. left != NullPtr)
00236 out << " left=" << nodes [x]. left;
00237 if (nodes [x]. right != NullPtr)
00238 out << " right=" << nodes [x]. right;
00239 if (nodes [x]. parent != NullPtr)
00240 out << " parent=" << nodes [x]. parent;
00241 if (nodes [x]. child != NullPtr)
00242 out << " child=" << nodes [x]. child;
00243 out << " deg=" << nodes [x]. degree << "\n";
00244
00245
00246 NodePtr child = nodes [x]. child;
00247 if (child == NullPtr)
00248 return;
00249 do
00250 {
00251 showGraph (out, depth + 1, child);
00252 child = nodes [child]. right;
00253 } while (child != nodes [x]. child);
00254 return;
00255 }
00256
00257 template <class element>
00258 inline FibonacciHeap<element>::FibonacciHeap (int maxSize):
00259 minRoot (NullPtr), nodeCount (0), nodes (maxSize), arrayPrepared (0)
00260 {
00261
00262
00263
00264
00265
00266
00267
00268 return;
00269 }
00270
00271 template <class element>
00272 inline FibonacciHeap<element>::~FibonacciHeap ()
00273 {
00274
00275
00276
00277
00278
00279
00280
00281 return;
00282 }
00283
00284 template <class element>
00285 inline FibonacciHeap<element>::FibonacciHeap (const FibonacciHeap<element> &)
00286 {
00287 throw "Copy constructor for a Fibonacci heap not implemented.";
00288 return;
00289 }
00290
00291 template <class element>
00292 inline FibonacciHeap<element> &FibonacciHeap<element>::operator =
00293 (const FibonacciHeap<element> &)
00294 {
00295 throw "Assignment operator for a Fibonacci heap not implemented.";
00296 return *this;
00297 }
00298
00299 template <class element>
00300 inline int FibonacciHeap<element>::Insert (const element &value)
00301 {
00302
00303 NodePtr nodePtr = nodeCount;
00304
00305
00306 if (!nodeCount)
00307 minValue = value;
00308 else if (value < minValue)
00309 minValue = value;
00310
00311
00312 Node &node = nodes [nodePtr];
00313 node. key = value;
00314 node. mark = false;
00315 node. degree = 0;
00316 node. number = nodeCount;
00317 node. parent = NullPtr;
00318 node. child = NullPtr;
00319
00320
00321 if (minRoot == NullPtr)
00322 {
00323 node. left = nodePtr;
00324 node. right = nodePtr;
00325 }
00326 else
00327 {
00328 node. left = nodes [minRoot]. left;
00329 node. right = minRoot;
00330 nodes [node. left]. right = nodePtr;
00331 nodes [node. right]. left = nodePtr;
00332 }
00333
00334
00335 if ((minRoot == NullPtr) || (value < nodes [minRoot]. key))
00336 minRoot = nodePtr;
00337
00338
00339 return nodeCount ++;
00340 }
00341
00342 template <class element>
00343 inline int FibonacciHeap<element>::Minimum () const
00344 {
00345 return minRoot;
00346 }
00347
00348 template <class element>
00349 inline const element &FibonacciHeap<element>::Value (int number) const
00350 {
00351 return nodes [number]. key;
00352 }
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363
00364
00365
00366
00367
00368
00369
00370
00371
00372
00373
00374
00375
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390
00391 template <class element>
00392 inline void FibonacciHeap<element>::Consolidate ()
00393 {
00394
00395 if (minRoot == NullPtr)
00396 return;
00397
00398
00399 NodePtr node = minRoot;
00400 int maxDegree = 0;
00401 do
00402 {
00403
00404 NodePtr x = node;
00405 int d = nodes [x]. degree;
00406
00407
00408 node = nodes [node]. right;
00409
00410
00411 while (arrayPrepared <= d)
00412 auxArray [arrayPrepared ++] = NullPtr;
00413
00414
00415 if (maxDegree <= d)
00416 maxDegree = d + 1;
00417
00418
00419 while (auxArray [d] != NullPtr)
00420 {
00421
00422 NodePtr y = auxArray [d];
00423
00424
00425 if (nodes [y]. key < nodes [x]. key)
00426 {
00427 NodePtr tmp = x;
00428 x = y;
00429 y = tmp;
00430 }
00431
00432
00433 nodes [y]. mark = false;
00434
00435
00436 nodes [y]. parent = x;
00437 NodePtr child = nodes [x]. child;
00438 if (child == NullPtr)
00439 {
00440 nodes [x]. child = y;
00441 nodes [y]. left = y;
00442 nodes [y]. right = y;
00443 }
00444 else
00445 {
00446 nodes [y]. left = child;
00447 nodes [y]. right = nodes [child]. right;
00448 nodes [child]. right = y;
00449 nodes [nodes [y]. right]. left = y;
00450 }
00451 ++ nodes [x]. degree;
00452
00453
00454 auxArray [d] = NullPtr;
00455
00456
00457 ++ d;
00458
00459
00460 if (arrayPrepared <= d)
00461 auxArray [arrayPrepared ++] = NullPtr;
00462
00463
00464 if (maxDegree <= d)
00465 maxDegree = d + 1;
00466 }
00467
00468
00469 auxArray [d] = x;
00470
00471 } while (node != minRoot);
00472
00473
00474 minRoot = NullPtr;
00475 for (int d = 0; d < maxDegree; ++ d)
00476 {
00477
00478 if (auxArray [d] == NullPtr)
00479 continue;
00480
00481
00482 NodePtr nodePtr = auxArray [d];
00483 auxArray [d] = NullPtr;
00484 Node &node = nodes [nodePtr];
00485
00486
00487 if (minRoot == NullPtr)
00488 {
00489 node. left = nodePtr;
00490 node. right = nodePtr;
00491 }
00492 else
00493 {
00494 node. left = minRoot;
00495 node. right = nodes [minRoot]. right;
00496 nodes [node. left]. right = nodePtr;
00497 nodes [node. right]. left = nodePtr;
00498 }
00499
00500
00501 if ((minRoot == NullPtr) ||
00502 (node. key < nodes [minRoot]. key))
00503 {
00504 minRoot = nodePtr;
00505 }
00506 }
00507 return;
00508 }
00509
00510 template <class element>
00511 inline element FibonacciHeap<element>::ExtractMinimum ()
00512 {
00513
00514 NodePtr nodePtr = minRoot;
00515 Node &node = nodes [minRoot];
00516
00517
00518
00519 NodePtr child = node. child;
00520 if (child != NullPtr)
00521 {
00522
00523 node. child = NullPtr;
00524
00525
00526 while (nodes [child]. parent != NullPtr)
00527 {
00528 nodes [child]. parent = NullPtr;
00529 child = nodes [child]. right;
00530 }
00531
00532
00533 NodePtr leftChild = child;
00534 NodePtr rightChild = nodes [child]. right;
00535 NodePtr leftRoot = nodePtr;
00536 NodePtr rightRoot = node. right;
00537 nodes [leftRoot]. right = rightChild;
00538 nodes [rightRoot]. left = leftChild;
00539 nodes [leftChild]. right = rightRoot;
00540 nodes [rightChild]. left = leftRoot;
00541 }
00542
00543
00544
00545 if (node. right != nodePtr)
00546 {
00547 minRoot = node. right;
00548 nodes [minRoot]. left = node. left;
00549 nodes [node. left]. right = minRoot;
00550 }
00551 else
00552 minRoot = NullPtr;
00553
00554
00555 node. left = NullPtr;
00556 node. right = NullPtr;
00557 node. parent = NullPtr;
00558 node. child = NullPtr;
00559 node. degree = -1;
00560
00561
00562 Consolidate ();
00563
00564 return node. key;
00565 }
00566
00567 template <class element>
00568 inline void FibonacciHeap<element>::Cut
00569 (const typename FibonacciHeap<element>::NodePtr &x,
00570 const typename FibonacciHeap<element>::NodePtr &y)
00571 {
00572
00573
00574 nodes [x]. parent = NullPtr;
00575 if (nodes [x]. right == x)
00576 {
00577 nodes [y]. child = NullPtr;
00578 }
00579
00580 else
00581 {
00582 NodePtr leftChild = nodes [x]. left;
00583 NodePtr rightChild = nodes [x]. right;
00584 nodes [y]. child = rightChild;
00585 nodes [leftChild]. right = rightChild;
00586 nodes [rightChild]. left = leftChild;
00587 }
00588
00589
00590 -- nodes [y]. degree;
00591
00592
00593 NodePtr leftRoot = minRoot;
00594 NodePtr rightRoot = nodes [minRoot]. right;
00595 nodes [x]. left = leftRoot;
00596 nodes [x]. right = rightRoot;
00597 nodes [leftRoot]. right = x;
00598 nodes [rightRoot]. left = x;
00599
00600
00601 nodes [x]. mark = false;
00602
00603 return;
00604 }
00605
00606 template <class element>
00607 inline void FibonacciHeap<element>::CascadingCut
00608 (typename FibonacciHeap<element>::NodePtr y)
00609 {
00610
00611 while (!(nodes [y]. parent == NullPtr))
00612 {
00613
00614
00615 if (!nodes [y]. mark)
00616 {
00617 nodes [y]. mark = true;
00618 return;
00619 }
00620
00621
00622
00623 NodePtr z = nodes [y]. parent;
00624 Cut (y, z);
00625 y = z;
00626 }
00627 return;
00628 }
00629
00630 template <class element>
00631 inline void FibonacciHeap<element>::DecreaseKey (int number,
00632 const element &value)
00633 {
00634
00635 NodePtr x (number);
00636
00637
00638 if (nodes [x]. degree == -1)
00639 return;
00640
00641
00642 if (value < minValue)
00643 minValue = value;
00644
00645
00646 nodes [x]. key = value;
00647
00648
00649 NodePtr y = nodes [x]. parent;
00650 if ((y != NullPtr) && (value < nodes [y]. key))
00651 {
00652 Cut (x, y);
00653 CascadingCut (y);
00654 }
00655
00656
00657 if (value < nodes [minRoot]. key)
00658 minRoot = x;
00659
00660 return;
00661 }
00662
00663 template <class element>
00664 inline void FibonacciHeap<element>::Delete (int number)
00665 {
00666 element value = minValue;
00667 DecreaseKey (number, value - 1);
00668 ExtractMinimum ();
00669 minValue = value;
00670 return;
00671 }
00672
00673
00674 }
00675 }
00676
00677 #endif // _FIBHEAP_H_
00678
00679
00680