Changeset 387:4406c93c862b in lemon0.x for src/include/fib_heap.h
 Timestamp:
 04/23/04 21:41:01 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@517
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/include/fib_heap.h
r373 r387 16 16 17 17 /** 18 This class implements the \e Fibonacci \e heap data structure. A \e 19 heap is a data structure for storing items with specified priorities,20 such that finding the item with minimum priority is efficient. In a21 heap one can change the priority of an item, and to add or erasean22 item .23 24 The methods \ref increase and \ref erase are not efficient , in25 case of many calls to these operations, it is better to use26 a binaryheap.18 This class implements the \e Fibonacci \e heap data structure. A \e heap 19 is a data structure for storing items with specified values called \e 20 priorities, such that finding the item with minimum priority with respect 21 to \e Compare is efficient. In a heap one can change the priority of an 22 item, add or erase an item, etc. 23 24 The methods \ref increase and \ref erase are not efficient in a Fibonacci 25 heap. In case of many calls to these operations, it is better to use a 26 \e binary \e heap. 27 27 28 /param Item The type of the items to be stored.29 /param Prio The type of the priority of the items.30 /param ItemIntMap A read and writable Item int map, for the usage of28 \param Item The type of the items to be stored. 29 \param Prio The type of the priority of the items. 30 \param ItemIntMap A read and writable Item int map, for the usage of 31 31 the heap. 32 /param Compare A class for the comparison of the priorities. The32 \param Compare A class for the comparison of the priorities. The 33 33 default is \c std::less<Prio>. 34 34 … … 47 47 #endif 48 48 class FibHeap { 49 public: 49 public: 50 50 typedef Prio PrioType; 51 51 … … 68 68 }; 69 69 70 public :71 72 70 FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {} 73 71 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0), … … 77 75 78 76 /** 79 Returns the number of items stored in the heap.77 Returns the number of items stored in the heap. 80 78 */ 81 79 int size() const { return num_items; } … … 84 82 85 83 /** 86 Returns true iff the heap stores no items.84 Returns \c true iff the heap stores no items. 87 85 */ 88 86 bool empty() const { return num_items==0; } 89 87 90 /// Item\c item gets to the heap with priority \c value independently if \c item was already there.91 92 /** 93 This method calls \ref push( item,value) if \c item is not94 stored in the heap , and it calls \ref decrease(it, \c value) or95 \ref increase( it, \c value) otherwise.96 */ 97 void set (Item const item, PrioType const value); //vigyazat: az implementacioban it van88 ///\c item gets to the heap with priority \c value independently if \c item was already there. 89 90 /** 91 This method calls \ref push(\c item, \c value) if \c item is not 92 stored in the heap and it calls \ref decrease(\c item, \c value) or 93 \ref increase(\c item, \c value) otherwise. 94 */ 95 void set (Item const item, PrioType const value); 98 96 99 97 ///Adds \c item to the heap with priority \c value. … … 103 101 \pre \c item must not be stored in the heap. 104 102 */ 105 void push (Item const it , PrioType const value); /*vigyazat: az implementacioban it van*/103 void push (Item const item, PrioType const value); 106 104 107 105 … … 130 128 \pre \c item must be in the heap. 131 129 */ 132 PrioType& operator[](const Item& it) { return container[iimap[it]].prio; } 130 PrioType& operator[](const Item& item) { 131 return container[iimap[item]].prio; 132 } 133 133 134 134 ///Returns the priority of \c item. … … 138 138 \pre \c item must be in the heap. 139 139 */ 140 const PrioType& operator[](const Item& it ) const {141 return container[iimap[it ]].prio;140 const PrioType& operator[](const Item& item) const { 141 return container[iimap[item]].prio; 142 142 } 143 143 … … 158 158 stored in the heap. It is quite inefficient in Fibonacci heaps. 159 159 */ 160 void erase (const Item& item); /*vigyazat: az implementacioban it van*/160 void erase (const Item& item); 161 161 162 162 ///Decreases the priority of \c item to \c value. … … 167 167 value w.r.t. Compare. 168 168 */ 169 void decrease (Item item, PrioType const value); /*vigyazat: az implementacioban it van*/169 void decrease (Item item, PrioType const value); 170 170 171 171 … … 175 175 This method sets the priority of \c item to \c value. Though 176 176 there is no precondition on the priority of \c item, this 177 method should be used only if one wants to\e increase177 method should be used only if there is a need to really \e increase 178 178 (w.r.t. Compare) the priority of \c item, because this 179 179 method is inefficient. 180 180 */ 181 void increase (Item it , PrioType const value) {182 erase(it );183 push(it , value);184 } 185 186 187 ///Tells if \c item is in, was in, or has notbeen in the heap.181 void increase (Item item, PrioType const value) { 182 erase(item); 183 push(item, value); 184 } 185 186 187 ///Tells if \c item is in, was already in, or has never been in the heap. 188 188 189 189 /** … … 193 193 get back to the heap again. 194 194 */ 195 state_enum state(const Item &it); /*vigyazat: az implementacioban it van*/ 196 195 state_enum state(const Item &item) const { 196 int i=iimap[item]; 197 if( i>=0 ) { 198 if ( container[i].in ) i=0; 199 else i=2; 200 } 201 return state_enum(i); 202 } 203 204 private: 205 206 void balance(); 207 void makeroot(int c); 208 void cut(int a, int b); 209 void cascade(int a); 210 void fuse(int a, int b); 211 void unlace(int a); 212 213 214 class store { 215 friend class FibHeap; 216 217 Item name; 218 int parent; 219 int left_neighbor; 220 int right_neighbor; 221 int child; 222 int degree; 223 bool marked; 224 bool in; 225 PrioType prio; 226 227 store() : parent(1), child(1), degree(), marked(false), in(true) {} 228 }; 229 }; 230 197 231 198 232 … … 201 235 // ********************************************************************** 202 236 203 204 void set (Item const it, PrioType const value) { 205 int i=iimap[it]; 206 if ( i >= 0 && container[i].in ) { 207 if ( comp(value, container[i].prio) ) decrease(it, value); 208 if ( comp(container[i].prio, value) ) increase(it, value); 209 } else push(it, value); 210 } 211 212 213 void push (Item const it, PrioType const value) { 214 int i=iimap[it]; 237 template <typename Item, typename Prio, typename ItemIntMap, 238 typename Compare> 239 void FibHeap<Item, Prio, ItemIntMap, Compare>::set 240 (Item const item, PrioType const value) 241 { 242 int i=iimap[item]; 243 if ( i >= 0 && container[i].in ) { 244 if ( comp(value, container[i].prio) ) decrease(item, value); 245 if ( comp(container[i].prio, value) ) increase(item, value); 246 } else push(item, value); 247 } 248 249 template <typename Item, typename Prio, typename ItemIntMap, 250 typename Compare> 251 void FibHeap<Item, Prio, ItemIntMap, Compare>::push 252 (Item const item, PrioType const value) { 253 int i=iimap[item]; 215 254 if ( i < 0 ) { 216 255 int s=container.size(); 217 iimap.set( it , s );256 iimap.set( item, s ); 218 257 store st; 219 st.name=it ;258 st.name=item; 220 259 container.push_back(st); 221 260 i=s; … … 241 280 } 242 281 243 244 void pop() { 282 template <typename Item, typename Prio, typename ItemIntMap, 283 typename Compare> 284 void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() { 245 285 /*The first case is that there are only one root.*/ 246 286 if ( container[minimum].left_neighbor==minimum ) { … … 273 313 } 274 314 275 276 void erase (const Item& it) { 277 int i=iimap[it]; 315 316 template <typename Item, typename Prio, typename ItemIntMap, 317 typename Compare> 318 void FibHeap<Item, Prio, ItemIntMap, Compare>::erase 319 (const Item& item) { 320 int i=iimap[item]; 278 321 279 322 if ( i >= 0 && container[i].in ) { … … 286 329 pop(); 287 330 } 288 } 289 290 291 void decrease (Item it, PrioType const value) { 292 int i=iimap[it]; 331 } 332 333 template <typename Item, typename Prio, typename ItemIntMap, 334 typename Compare> 335 void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease 336 (Item item, PrioType const value) { 337 int i=iimap[item]; 293 338 container[i].prio=value; 294 339 int p=container[i].parent; … … 299 344 } 300 345 if ( comp(value, container[minimum].prio) ) minimum=i; 301 } 302 303 304 state_enum state(const Item &it) const { 305 int i=iimap[it]; 306 if( i>=0 ) { 307 if ( container[i].in ) i=0; 308 else i=2; 309 } 310 return state_enum(i); 311 } 312 313 314 private: 315 316 void balance() { 346 } 347 348 349 template <typename Item, typename Prio, typename ItemIntMap, 350 typename Compare> 351 void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() { 317 352 318 353 int maxdeg=int( floor( 2.08*log(double(container.size()))))+1; … … 357 392 } 358 393 359 360 void makeroot (int c) { 394 template <typename Item, typename Prio, typename ItemIntMap, 395 typename Compare> 396 void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot 397 (int c) { 361 398 int s=c; 362 399 do { … … 365 402 } while ( s != c ); 366 403 } 367 368 369 void cut (int a, int b) { 370 /* 371 *Replacing a from the children of b. 372 */ 373 container[b].degree; 374 375 if ( container[b].degree !=0 ) { 376 int child=container[b].child; 377 if ( child==a ) 378 container[b].child=container[child].right_neighbor; 379 unlace(a); 380 } 381 382 383 /*Lacing a to the roots.*/ 384 int right=container[minimum].right_neighbor; 385 container[minimum].right_neighbor=a; 386 container[a].left_neighbor=minimum; 387 container[a].right_neighbor=right; 388 container[right].left_neighbor=a; 389 390 container[a].parent=1; 391 container[a].marked=false; 392 } 393 394 395 void cascade (int a) 404 405 406 template <typename Item, typename Prio, typename ItemIntMap, 407 typename Compare> 408 void FibHeap<Item, Prio, ItemIntMap, Compare>::cut 409 (int a, int b) { 410 /* 411 *Replacing a from the children of b. 412 */ 413 container[b].degree; 414 415 if ( container[b].degree !=0 ) { 416 int child=container[b].child; 417 if ( child==a ) 418 container[b].child=container[child].right_neighbor; 419 unlace(a); 420 } 421 422 423 /*Lacing a to the roots.*/ 424 int right=container[minimum].right_neighbor; 425 container[minimum].right_neighbor=a; 426 container[a].left_neighbor=minimum; 427 container[a].right_neighbor=right; 428 container[right].left_neighbor=a; 429 430 container[a].parent=1; 431 container[a].marked=false; 432 } 433 434 435 template <typename Item, typename Prio, typename ItemIntMap, 436 typename Compare> 437 void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade 438 (int a) 396 439 { 397 440 if ( container[a].parent!=1 ) { … … 407 450 408 451 409 void fuse (int a, int b) { 452 template <typename Item, typename Prio, typename ItemIntMap, 453 typename Compare> 454 void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse 455 (int a, int b) { 410 456 unlace(b); 411 457 … … 431 477 } 432 478 433 434 /* 435 *It is invoked only if a has siblings. 436 */ 437 void unlace (int a) { 479 480 /* 481 *It is invoked only if a has siblings. 482 */ 483 template <typename Item, typename Prio, typename ItemIntMap, 484 typename Compare> 485 void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace 486 (int a) { 438 487 int leftn=container[a].left_neighbor; 439 488 int rightn=container[a].right_neighbor; 440 489 container[leftn].right_neighbor=rightn; 441 490 container[rightn].left_neighbor=leftn; 442 } 443 444 445 class store { 446 friend class FibHeap; 447 448 Item name; 449 int parent; 450 int left_neighbor; 451 int right_neighbor; 452 int child; 453 int degree; 454 bool marked; 455 bool in; 456 PrioType prio; 457 458 store() : parent(1), child(1), degree(), marked(false), in(true) {} 459 }; 460 461 }; 491 } 462 492 463 493 } //namespace hugo
Note: See TracChangeset
for help on using the changeset viewer.