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