Changeset 2547:f393a8162688 in lemon-0.x for lemon/fib_heap.h
- Timestamp:
- 12/27/07 14:40:16 (16 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3424
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/fib_heap.h
r2529 r2547 42 42 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci 43 43 ///heap. In case of many calls to these operations, it is better to use a 44 ///\ e binary \e heap.44 ///\ref BinHeap "binary heap". 45 45 /// 46 ///\param Prio Type of the priority of the items.47 ///\param ItemIntMap A read and writable Item int map, used internally46 ///\param _Prio Type of the priority of the items. 47 ///\param _ItemIntMap A read and writable Item int map, used internally 48 48 ///to handle the cross references. 49 ///\param Compare A class for the ordering of the priorities. The50 ///default is \c std::less< Prio>.49 ///\param _Compare A class for the ordering of the priorities. The 50 ///default is \c std::less<_Prio>. 51 51 /// 52 52 ///\sa BinHeap … … 55 55 56 56 #ifdef DOXYGEN 57 template <typename Prio,58 typename ItemIntMap,59 typename Compare>57 template <typename _Prio, 58 typename _ItemIntMap, 59 typename _Compare> 60 60 #else 61 template <typename Prio,62 typename ItemIntMap,63 typename Compare = std::less<Prio> >61 template <typename _Prio, 62 typename _ItemIntMap, 63 typename _Compare = std::less<_Prio> > 64 64 #endif 65 65 class FibHeap { 66 66 public: 67 typedef _ItemIntMap ItemIntMap; 68 typedef _Prio Prio; 67 69 typedef typename ItemIntMap::Key Item; 68 typedef Prio PrioType; 70 typedef std::pair<Item,Prio> Pair; 71 typedef _Compare Compare; 69 72 70 73 private: … … 79 82 public: 80 83 ///Status of the nodes 81 enum state_enum{84 enum State { 82 85 ///The node is in the heap 83 86 IN_HEAP = 0, … … 100 103 /// internally to handle the cross references. \c _comp is an 101 104 /// object for ordering of the priorities. 102 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),103 105 FibHeap(ItemIntMap &_iimap, const Compare &_comp) 106 : minimum(0), iimap(_iimap), comp(_comp), num_items() {} 104 107 105 108 /// \brief The number of items stored in the heap. … … 129 132 /// stored in the heap and it calls \ref decrease(\c item, \c value) or 130 133 /// \ref increase(\c item, \c value) otherwise. 131 void set (Item const item, PrioType const value); 134 void set (const Item& item, const Prio& value) { 135 int i=iimap[item]; 136 if ( i >= 0 && container[i].in ) { 137 if ( comp(value, container[i].prio) ) decrease(item, value); 138 if ( comp(container[i].prio, value) ) increase(item, value); 139 } else push(item, value); 140 } 132 141 133 142 /// \brief Adds \c item to the heap with priority \c value. … … 135 144 /// Adds \c item to the heap with priority \c value. 136 145 /// \pre \c item must not be stored in the heap. 137 void push (Item const item, PrioType const value); 138 139 /// \brief Returns the item with minimum priority relative to \c Compare. 140 /// 141 /// This method returns the item with minimum priority relative to \c 142 /// Compare. 143 /// \pre The heap must be nonempty. 144 Item top() const { return container[minimum].name; } 145 146 /// \brief Returns the minimum priority relative to \c Compare. 147 /// 148 /// It returns the minimum priority relative to \c Compare. 149 /// \pre The heap must be nonempty. 150 PrioType prio() const { return container[minimum].prio; } 151 152 /// \brief Returns the priority of \c item. 153 /// 154 /// This function returns the priority of \c item. 155 /// \pre \c item must be in the heap. 156 PrioType& operator[](const Item& item) { 157 return container[iimap[item]].prio; 158 } 159 160 /// \brief Returns the priority of \c item. 161 /// 162 /// It returns the priority of \c item. 163 /// \pre \c item must be in the heap. 164 const PrioType& operator[](const Item& item) const { 165 return container[iimap[item]].prio; 166 } 167 168 169 /// \brief Deletes the item with minimum priority relative to \c Compare. 170 /// 171 /// This method deletes the item with minimum priority relative to \c 172 /// Compare from the heap. 173 /// \pre The heap must be non-empty. 174 void pop(); 175 176 /// \brief Deletes \c item from the heap. 177 /// 178 /// This method deletes \c item from the heap, if \c item was already 179 /// stored in the heap. It is quite inefficient in Fibonacci heaps. 180 void erase (const Item& item); 181 182 /// \brief Decreases the priority of \c item to \c value. 183 /// 184 /// This method decreases the priority of \c item to \c value. 185 /// \pre \c item must be stored in the heap with priority at least \c 186 /// value relative to \c Compare. 187 void decrease (Item item, PrioType const value); 188 189 /// \brief Increases the priority of \c item to \c value. 190 /// 191 /// This method sets the priority of \c item to \c value. Though 192 /// there is no precondition on the priority of \c item, this 193 /// method should be used only if it is indeed necessary to increase 194 /// (relative to \c Compare) the priority of \c item, because this 195 /// method is inefficient. 196 void increase (Item item, PrioType const value) { 197 erase(item); 198 push(item, value); 199 } 200 201 202 /// \brief Returns if \c item is in, has already been in, or has never 203 /// been in the heap. 204 /// 205 /// This method returns PRE_HEAP if \c item has never been in the 206 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 207 /// otherwise. In the latter case it is possible that \c item will 208 /// get back to the heap again. 209 state_enum state(const Item &item) const { 210 int i=iimap[item]; 211 if( i>=0 ) { 212 if ( container[i].in ) i=0; 213 else i=-2; 214 } 215 return state_enum(i); 216 } 217 218 /// \brief Sets the state of the \c item in the heap. 219 /// 220 /// Sets the state of the \c item in the heap. It can be used to 221 /// manually clear the heap when it is important to achive the 222 /// better time complexity. 223 /// \param i The item. 224 /// \param st The state. It should not be \c IN_HEAP. 225 void state(const Item& i, state_enum st) { 226 switch (st) { 227 case POST_HEAP: 228 case PRE_HEAP: 229 if (state(i) == IN_HEAP) { 230 erase(i); 231 } 232 iimap[i] = st; 233 break; 234 case IN_HEAP: 235 break; 236 } 237 } 238 239 private: 240 241 void balance(); 242 void makeroot(int c); 243 void cut(int a, int b); 244 void cascade(int a); 245 void fuse(int a, int b); 246 void unlace(int a); 247 248 249 class store { 250 friend class FibHeap; 251 252 Item name; 253 int parent; 254 int left_neighbor; 255 int right_neighbor; 256 int child; 257 int degree; 258 bool marked; 259 bool in; 260 PrioType prio; 261 262 store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 263 }; 264 }; 265 266 267 268 // ********************************************************************** 269 // IMPLEMENTATIONS 270 // ********************************************************************** 271 272 template <typename Prio, typename ItemIntMap, 273 typename Compare> 274 void FibHeap<Prio, ItemIntMap, Compare>::set 275 (Item const item, PrioType const value) 276 { 277 int i=iimap[item]; 278 if ( i >= 0 && container[i].in ) { 279 if ( comp(value, container[i].prio) ) decrease(item, value); 280 if ( comp(container[i].prio, value) ) increase(item, value); 281 } else push(item, value); 282 } 283 284 template <typename Prio, typename ItemIntMap, 285 typename Compare> 286 void FibHeap<Prio, ItemIntMap, Compare>::push 287 (Item const item, PrioType const value) { 146 void push (const Item& item, const Prio& value) { 288 147 int i=iimap[item]; 289 148 if ( i < 0 ) { … … 315 174 } 316 175 317 template <typename Prio, typename ItemIntMap, 318 typename Compare> 319 void FibHeap<Prio, ItemIntMap, Compare>::pop() { 176 /// \brief Returns the item with minimum priority relative to \c Compare. 177 /// 178 /// This method returns the item with minimum priority relative to \c 179 /// Compare. 180 /// \pre The heap must be nonempty. 181 Item top() const { return container[minimum].name; } 182 183 /// \brief Returns the minimum priority relative to \c Compare. 184 /// 185 /// It returns the minimum priority relative to \c Compare. 186 /// \pre The heap must be nonempty. 187 const Prio& prio() const { return container[minimum].prio; } 188 189 /// \brief Returns the priority of \c item. 190 /// 191 /// It returns the priority of \c item. 192 /// \pre \c item must be in the heap. 193 const Prio& operator[](const Item& item) const { 194 return container[iimap[item]].prio; 195 } 196 197 /// \brief Deletes the item with minimum priority relative to \c Compare. 198 /// 199 /// This method deletes the item with minimum priority relative to \c 200 /// Compare from the heap. 201 /// \pre The heap must be non-empty. 202 void pop() { 320 203 /*The first case is that there are only one root.*/ 321 204 if ( container[minimum].left_neighbor==minimum ) { … … 334 217 int child=container[minimum].child; 335 218 int last_child=container[child].left_neighbor; 336 219 337 220 makeroot(child); 338 221 … … 348 231 } 349 232 350 351 template <typename Prio, typename ItemIntMap,352 typename Compare>353 void FibHeap<Prio, ItemIntMap, Compare>::erase354 (const Item& item) {233 /// \brief Deletes \c item from the heap. 234 /// 235 /// This method deletes \c item from the heap, if \c item was already 236 /// stored in the heap. It is quite inefficient in Fibonacci heaps. 237 void erase (const Item& item) { 355 238 int i=iimap[item]; 356 239 … … 364 247 pop(); 365 248 } 366 } 367 368 template <typename Prio, typename ItemIntMap, 369 typename Compare> 370 void FibHeap<Prio, ItemIntMap, Compare>::decrease 371 (Item item, PrioType const value) { 249 } 250 251 /// \brief Decreases the priority of \c item to \c value. 252 /// 253 /// This method decreases the priority of \c item to \c value. 254 /// \pre \c item must be stored in the heap with priority at least \c 255 /// value relative to \c Compare. 256 void decrease (Item item, const Prio& value) { 372 257 int i=iimap[item]; 373 258 container[i].prio=value; … … 379 264 } 380 265 if ( comp(value, container[minimum].prio) ) minimum=i; 381 } 382 383 384 template <typename Prio, typename ItemIntMap, 385 typename Compare> 386 void FibHeap<Prio, ItemIntMap, Compare>::balance() { 387 388 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; 266 } 267 268 /// \brief Increases the priority of \c item to \c value. 269 /// 270 /// This method sets the priority of \c item to \c value. Though 271 /// there is no precondition on the priority of \c item, this 272 /// method should be used only if it is indeed necessary to increase 273 /// (relative to \c Compare) the priority of \c item, because this 274 /// method is inefficient. 275 void increase (Item item, const Prio& value) { 276 erase(item); 277 push(item, value); 278 } 279 280 281 /// \brief Returns if \c item is in, has already been in, or has never 282 /// been in the heap. 283 /// 284 /// This method returns PRE_HEAP if \c item has never been in the 285 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 286 /// otherwise. In the latter case it is possible that \c item will 287 /// get back to the heap again. 288 State state(const Item &item) const { 289 int i=iimap[item]; 290 if( i>=0 ) { 291 if ( container[i].in ) i=0; 292 else i=-2; 293 } 294 return State(i); 295 } 296 297 /// \brief Sets the state of the \c item in the heap. 298 /// 299 /// Sets the state of the \c item in the heap. It can be used to 300 /// manually clear the heap when it is important to achive the 301 /// better time complexity. 302 /// \param i The item. 303 /// \param st The state. It should not be \c IN_HEAP. 304 void state(const Item& i, State st) { 305 switch (st) { 306 case POST_HEAP: 307 case PRE_HEAP: 308 if (state(i) == IN_HEAP) { 309 erase(i); 310 } 311 iimap[i] = st; 312 break; 313 case IN_HEAP: 314 break; 315 } 316 } 317 318 private: 319 320 void balance() { 321 322 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; 389 323 390 std::vector<int> A(maxdeg,-1);391 392 /*393 *Recall that now minimum does not point to the minimum prio element.394 *We set minimum to this during balance().395 */396 int anchor=container[minimum].left_neighbor;397 int next=minimum;398 bool end=false;324 std::vector<int> A(maxdeg,-1); 325 326 /* 327 *Recall that now minimum does not point to the minimum prio element. 328 *We set minimum to this during balance(). 329 */ 330 int anchor=container[minimum].left_neighbor; 331 int next=minimum; 332 bool end=false; 399 333 400 334 do { 401 335 int active=next; 402 336 if ( anchor==active ) end=true; … … 415 349 } 416 350 A[d]=active; 417 } while ( !end ); 418 419 420 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent; 421 int s=minimum; 422 int m=minimum; 423 do { 424 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; 425 s=container[s].right_neighbor; 426 } while ( s != m ); 427 } 428 429 template <typename Prio, typename ItemIntMap, 430 typename Compare> 431 void FibHeap<Prio, ItemIntMap, Compare>::makeroot 432 (int c) { 351 } while ( !end ); 352 353 354 while ( container[minimum].parent >=0 ) 355 minimum=container[minimum].parent; 356 int s=minimum; 357 int m=minimum; 358 do { 359 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; 360 s=container[s].right_neighbor; 361 } while ( s != m ); 362 } 363 364 void makeroot(int c) { 433 365 int s=c; 434 366 do { … … 437 369 } while ( s != c ); 438 370 } 439 440 441 template <typename Prio, typename ItemIntMap, 442 typename Compare> 443 void FibHeap<Prio, ItemIntMap, Compare>::cut 444 (int a, int b) { 445 /* 446 *Replacing a from the children of b. 447 */ 448 --container[b].degree; 449 450 if ( container[b].degree !=0 ) { 451 int child=container[b].child; 452 if ( child==a ) 453 container[b].child=container[child].right_neighbor; 454 unlace(a); 455 } 456 457 458 /*Lacing a to the roots.*/ 459 int right=container[minimum].right_neighbor; 460 container[minimum].right_neighbor=a; 461 container[a].left_neighbor=minimum; 462 container[a].right_neighbor=right; 463 container[right].left_neighbor=a; 464 465 container[a].parent=-1; 466 container[a].marked=false; 467 } 468 469 470 template <typename Prio, typename ItemIntMap, 471 typename Compare> 472 void FibHeap<Prio, ItemIntMap, Compare>::cascade 473 (int a) 474 { 371 372 void cut(int a, int b) { 373 /* 374 *Replacing a from the children of b. 375 */ 376 --container[b].degree; 377 378 if ( container[b].degree !=0 ) { 379 int child=container[b].child; 380 if ( child==a ) 381 container[b].child=container[child].right_neighbor; 382 unlace(a); 383 } 384 385 386 /*Lacing a to the roots.*/ 387 int right=container[minimum].right_neighbor; 388 container[minimum].right_neighbor=a; 389 container[a].left_neighbor=minimum; 390 container[a].right_neighbor=right; 391 container[right].left_neighbor=a; 392 393 container[a].parent=-1; 394 container[a].marked=false; 395 } 396 397 void cascade(int a) { 475 398 if ( container[a].parent!=-1 ) { 476 399 int p=container[a].parent; … … 484 407 } 485 408 486 487 template <typename Prio, typename ItemIntMap, 488 typename Compare> 489 void FibHeap<Prio, ItemIntMap, Compare>::fuse 490 (int a, int b) { 409 void fuse(int a, int b) { 491 410 unlace(b); 492 411 … … 512 431 } 513 432 514 515 /* 516 *It is invoked only if a has siblings. 517 */ 518 template <typename Prio, typename ItemIntMap, 519 typename Compare> 520 void FibHeap<Prio, ItemIntMap, Compare>::unlace 521 (int a) { 433 /* 434 *It is invoked only if a has siblings. 435 */ 436 void unlace(int a) { 522 437 int leftn=container[a].left_neighbor; 523 438 int rightn=container[a].right_neighbor; 524 439 container[leftn].right_neighbor=rightn; 525 440 container[rightn].left_neighbor=leftn; 526 } 527 441 } 442 443 444 class store { 445 friend class FibHeap; 446 447 Item name; 448 int parent; 449 int left_neighbor; 450 int right_neighbor; 451 int child; 452 int degree; 453 bool marked; 454 bool in; 455 Prio prio; 456 457 store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 458 }; 459 }; 528 460 529 461 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.