00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_FIB_HEAP_H
00020 #define LEMON_FIB_HEAP_H
00021
00025
00026 #include <vector>
00027 #include <functional>
00028 #include <cmath>
00029
00030 namespace lemon {
00031
00033
00035
00056
00057 #ifdef DOXYGEN
00058 template <typename Item,
00059 typename Prio,
00060 typename ItemIntMap,
00061 typename Compare>
00062 #else
00063 template <typename Item,
00064 typename Prio,
00065 typename ItemIntMap,
00066 typename Compare = std::less<Prio> >
00067 #endif
00068 class FibHeap {
00069 public:
00070 typedef Prio PrioType;
00071
00072 private:
00073 class store;
00074
00075 std::vector<store> container;
00076 int minimum;
00077 ItemIntMap &iimap;
00078 Compare comp;
00079 int num_items;
00080
00081 public:
00083 enum state_enum {
00085 IN_HEAP = 0,
00087 PRE_HEAP = -1,
00089 POST_HEAP = -2
00090 };
00091
00096 explicit FibHeap(ItemIntMap &_iimap)
00097 : minimum(0), iimap(_iimap), num_items() {}
00098
00104 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
00105 iimap(_iimap), comp(_comp), num_items() {}
00106
00110 int size() const { return num_items; }
00111
00115 bool empty() const { return num_items==0; }
00116
00120 void clear() {
00121 if (num_items != 0) {
00122 for (int i = 0; i < (int)container.size(); ++i) {
00123 iimap[container[i].name] = -2;
00124 }
00125 }
00126 container.clear(); minimum = 0; num_items = 0;
00127 }
00128
00135 void set (Item const item, PrioType const value);
00136
00141 void push (Item const item, PrioType const value);
00142
00148 Item top() const { return container[minimum].name; }
00149
00154 PrioType prio() const { return container[minimum].prio; }
00155
00160 PrioType& operator[](const Item& item) {
00161 return container[iimap[item]].prio;
00162 }
00163
00168 const PrioType& operator[](const Item& item) const {
00169 return container[iimap[item]].prio;
00170 }
00171
00172
00178 void pop();
00179
00184 void erase (const Item& item);
00185
00191 void decrease (Item item, PrioType const value);
00192
00200 void increase (Item item, PrioType const value) {
00201 erase(item);
00202 push(item, value);
00203 }
00204
00205
00213 state_enum state(const Item &item) const {
00214 int i=iimap[item];
00215 if( i>=0 ) {
00216 if ( container[i].in ) i=0;
00217 else i=-2;
00218 }
00219 return state_enum(i);
00220 }
00221
00229 void state(const Item& i, state_enum st) {
00230 switch (st) {
00231 case POST_HEAP:
00232 case PRE_HEAP:
00233 if (state(i) == IN_HEAP) {
00234 erase(i);
00235 }
00236 iimap[i] = st;
00237 break;
00238 case IN_HEAP:
00239 break;
00240 }
00241 }
00242
00243 private:
00244
00245 void balance();
00246 void makeroot(int c);
00247 void cut(int a, int b);
00248 void cascade(int a);
00249 void fuse(int a, int b);
00250 void unlace(int a);
00251
00252
00253 class store {
00254 friend class FibHeap;
00255
00256 Item name;
00257 int parent;
00258 int left_neighbor;
00259 int right_neighbor;
00260 int child;
00261 int degree;
00262 bool marked;
00263 bool in;
00264 PrioType prio;
00265
00266 store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
00267 };
00268 };
00269
00270
00271
00272
00273
00274
00275
00276 template <typename Item, typename Prio, typename ItemIntMap,
00277 typename Compare>
00278 void FibHeap<Item, Prio, ItemIntMap, Compare>::set
00279 (Item const item, PrioType const value)
00280 {
00281 int i=iimap[item];
00282 if ( i >= 0 && container[i].in ) {
00283 if ( comp(value, container[i].prio) ) decrease(item, value);
00284 if ( comp(container[i].prio, value) ) increase(item, value);
00285 } else push(item, value);
00286 }
00287
00288 template <typename Item, typename Prio, typename ItemIntMap,
00289 typename Compare>
00290 void FibHeap<Item, Prio, ItemIntMap, Compare>::push
00291 (Item const item, PrioType const value) {
00292 int i=iimap[item];
00293 if ( i < 0 ) {
00294 int s=container.size();
00295 iimap.set( item, s );
00296 store st;
00297 st.name=item;
00298 container.push_back(st);
00299 i=s;
00300 } else {
00301 container[i].parent=container[i].child=-1;
00302 container[i].degree=0;
00303 container[i].in=true;
00304 container[i].marked=false;
00305 }
00306
00307 if ( num_items ) {
00308 container[container[minimum].right_neighbor].left_neighbor=i;
00309 container[i].right_neighbor=container[minimum].right_neighbor;
00310 container[minimum].right_neighbor=i;
00311 container[i].left_neighbor=minimum;
00312 if ( comp( value, container[minimum].prio) ) minimum=i;
00313 } else {
00314 container[i].right_neighbor=container[i].left_neighbor=i;
00315 minimum=i;
00316 }
00317 container[i].prio=value;
00318 ++num_items;
00319 }
00320
00321 template <typename Item, typename Prio, typename ItemIntMap,
00322 typename Compare>
00323 void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
00324
00325 if ( container[minimum].left_neighbor==minimum ) {
00326 container[minimum].in=false;
00327 if ( container[minimum].degree!=0 ) {
00328 makeroot(container[minimum].child);
00329 minimum=container[minimum].child;
00330 balance();
00331 }
00332 } else {
00333 int right=container[minimum].right_neighbor;
00334 unlace(minimum);
00335 container[minimum].in=false;
00336 if ( container[minimum].degree > 0 ) {
00337 int left=container[minimum].left_neighbor;
00338 int child=container[minimum].child;
00339 int last_child=container[child].left_neighbor;
00340
00341 makeroot(child);
00342
00343 container[left].right_neighbor=child;
00344 container[child].left_neighbor=left;
00345 container[right].left_neighbor=last_child;
00346 container[last_child].right_neighbor=right;
00347 }
00348 minimum=right;
00349 balance();
00350 }
00351 --num_items;
00352 }
00353
00354
00355 template <typename Item, typename Prio, typename ItemIntMap,
00356 typename Compare>
00357 void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
00358 (const Item& item) {
00359 int i=iimap[item];
00360
00361 if ( i >= 0 && container[i].in ) {
00362 if ( container[i].parent!=-1 ) {
00363 int p=container[i].parent;
00364 cut(i,p);
00365 cascade(p);
00366 }
00367 minimum=i;
00368 pop();
00369 }
00370 }
00371
00372 template <typename Item, typename Prio, typename ItemIntMap,
00373 typename Compare>
00374 void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
00375 (Item item, PrioType const value) {
00376 int i=iimap[item];
00377 container[i].prio=value;
00378 int p=container[i].parent;
00379
00380 if ( p!=-1 && comp(value, container[p].prio) ) {
00381 cut(i,p);
00382 cascade(p);
00383 }
00384 if ( comp(value, container[minimum].prio) ) minimum=i;
00385 }
00386
00387
00388 template <typename Item, typename Prio, typename ItemIntMap,
00389 typename Compare>
00390 void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
00391
00392 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
00393
00394 std::vector<int> A(maxdeg,-1);
00395
00396
00397
00398
00399
00400 int anchor=container[minimum].left_neighbor;
00401 int next=minimum;
00402 bool end=false;
00403
00404 do {
00405 int active=next;
00406 if ( anchor==active ) end=true;
00407 int d=container[active].degree;
00408 next=container[active].right_neighbor;
00409
00410 while (A[d]!=-1) {
00411 if( comp(container[active].prio, container[A[d]].prio) ) {
00412 fuse(active,A[d]);
00413 } else {
00414 fuse(A[d],active);
00415 active=A[d];
00416 }
00417 A[d]=-1;
00418 ++d;
00419 }
00420 A[d]=active;
00421 } while ( !end );
00422
00423
00424 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
00425 int s=minimum;
00426 int m=minimum;
00427 do {
00428 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
00429 s=container[s].right_neighbor;
00430 } while ( s != m );
00431 }
00432
00433 template <typename Item, typename Prio, typename ItemIntMap,
00434 typename Compare>
00435 void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
00436 (int c) {
00437 int s=c;
00438 do {
00439 container[s].parent=-1;
00440 s=container[s].right_neighbor;
00441 } while ( s != c );
00442 }
00443
00444
00445 template <typename Item, typename Prio, typename ItemIntMap,
00446 typename Compare>
00447 void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
00448 (int a, int b) {
00449
00450
00451
00452 --container[b].degree;
00453
00454 if ( container[b].degree !=0 ) {
00455 int child=container[b].child;
00456 if ( child==a )
00457 container[b].child=container[child].right_neighbor;
00458 unlace(a);
00459 }
00460
00461
00462
00463 int right=container[minimum].right_neighbor;
00464 container[minimum].right_neighbor=a;
00465 container[a].left_neighbor=minimum;
00466 container[a].right_neighbor=right;
00467 container[right].left_neighbor=a;
00468
00469 container[a].parent=-1;
00470 container[a].marked=false;
00471 }
00472
00473
00474 template <typename Item, typename Prio, typename ItemIntMap,
00475 typename Compare>
00476 void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
00477 (int a)
00478 {
00479 if ( container[a].parent!=-1 ) {
00480 int p=container[a].parent;
00481
00482 if ( container[a].marked==false ) container[a].marked=true;
00483 else {
00484 cut(a,p);
00485 cascade(p);
00486 }
00487 }
00488 }
00489
00490
00491 template <typename Item, typename Prio, typename ItemIntMap,
00492 typename Compare>
00493 void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
00494 (int a, int b) {
00495 unlace(b);
00496
00497
00498 container[b].parent=a;
00499
00500 if (container[a].degree==0) {
00501 container[b].left_neighbor=b;
00502 container[b].right_neighbor=b;
00503 container[a].child=b;
00504 } else {
00505 int child=container[a].child;
00506 int last_child=container[child].left_neighbor;
00507 container[child].left_neighbor=b;
00508 container[b].right_neighbor=child;
00509 container[last_child].right_neighbor=b;
00510 container[b].left_neighbor=last_child;
00511 }
00512
00513 ++container[a].degree;
00514
00515 container[b].marked=false;
00516 }
00517
00518
00519
00520
00521
00522 template <typename Item, typename Prio, typename ItemIntMap,
00523 typename Compare>
00524 void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
00525 (int a) {
00526 int leftn=container[a].left_neighbor;
00527 int rightn=container[a].right_neighbor;
00528 container[leftn].right_neighbor=rightn;
00529 container[rightn].left_neighbor=leftn;
00530 }
00531
00532
00533 }
00534
00535 #endif //LEMON_FIB_HEAP_H
00536