Changeset 730:9f529abcaebf in lemon for lemon/fib_heap.h
- Timestamp:
- 06/11/09 23:13:24 (15 years ago)
- Branch:
- default
- Children:
- 733:7439dc5fe1b9, 738:9e54e3b27db0, 740:7bda7860e0a8, 743:c9b9da1a90a0, 748:d1a9224f1e30, 756:0747f332c478, 760:4ac30454f1c1, 765:703ebf476a1d, 805:b31e130db13d
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/fib_heap.h
r728 r730 37 37 ///is a data structure for storing items with specified values called \e 38 38 ///priorities in such a way that finding the item with minimum priority is 39 ///efficient. \c C omparespecifies the ordering of the priorities. In a heap39 ///efficient. \c CMP specifies the ordering of the priorities. In a heap 40 40 ///one can change the priority of an item, add or erase an item, etc. 41 41 /// … … 44 44 ///\ref BinHeap "binary heap". 45 45 /// 46 ///\param _PrioType of the priority of the items.47 ///\param _ItemIntMapA read and writable Item int map, used internally46 ///\param PRIO Type of the priority of the items. 47 ///\param IM A read and writable Item int map, used internally 48 48 ///to handle the cross references. 49 ///\param _CompareA class for the ordering of the priorities. The50 ///default is \c std::less< _Prio>.49 ///\param CMP A class for the ordering of the priorities. The 50 ///default is \c std::less<PRIO>. 51 51 /// 52 52 ///\sa BinHeap 53 53 ///\sa Dijkstra 54 54 #ifdef DOXYGEN 55 template <typename _Prio, 56 typename _ItemIntMap, 57 typename _Compare> 55 template <typename PRIO, typename IM, typename CMP> 58 56 #else 59 template <typename _Prio, 60 typename _ItemIntMap, 61 typename _Compare = std::less<_Prio> > 57 template <typename PRIO, typename IM, typename CMP = std::less<PRIO> > 62 58 #endif 63 59 class FibHeap { 64 60 public: 65 61 ///\e 66 typedef _ItemIntMapItemIntMap;62 typedef IM ItemIntMap; 67 63 ///\e 68 typedef _PrioPrio;64 typedef PRIO Prio; 69 65 ///\e 70 66 typedef typename ItemIntMap::Key Item; … … 72 68 typedef std::pair<Item,Prio> Pair; 73 69 ///\e 74 typedef _CompareCompare;70 typedef CMP Compare; 75 71 76 72 private: 77 class store;78 79 std::vector< store> container;80 int minimum;81 ItemIntMap & iimap;82 Compare comp;83 int num_items;73 class Store; 74 75 std::vector<Store> _data; 76 int _minimum; 77 ItemIntMap &_iim; 78 Compare _comp; 79 int _num; 84 80 85 81 public: 86 ///Status of the nodes 82 83 /// \brief Type to represent the items states. 84 /// 85 /// Each Item element have a state associated to it. It may be "in heap", 86 /// "pre heap" or "post heap". The latter two are indifferent from the 87 /// heap's point of view, but may be useful to the user. 88 /// 89 /// The item-int map must be initialized in such way that it assigns 90 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 87 91 enum State { 88 ///The node is in the heap 89 IN_HEAP = 0, 90 ///The node has never been in the heap 91 PRE_HEAP = -1, 92 ///The node was in the heap but it got out of it 93 POST_HEAP = -2 92 IN_HEAP = 0, ///< = 0. 93 PRE_HEAP = -1, ///< = -1. 94 POST_HEAP = -2 ///< = -2. 94 95 }; 95 96 96 97 /// \brief The constructor 97 98 /// 98 /// \c _iimap should be given to the constructor, since it is99 /// \c map should be given to the constructor, since it is 99 100 /// used internally to handle the cross references. 100 explicit FibHeap(ItemIntMap & _iimap)101 : minimum(0), iimap(_iimap), num_items() {}101 explicit FibHeap(ItemIntMap &map) 102 : _minimum(0), _iim(map), _num() {} 102 103 103 104 /// \brief The constructor 104 105 /// 105 /// \c _iimap should be given to the constructor, since it is used106 /// internally to handle the cross references. \c _comp is an106 /// \c map should be given to the constructor, since it is used 107 /// internally to handle the cross references. \c comp is an 107 108 /// object for ordering of the priorities. 108 FibHeap(ItemIntMap & _iimap, const Compare &_comp)109 : minimum(0), iimap(_iimap), comp(_comp), num_items() {}109 FibHeap(ItemIntMap &map, const Compare &comp) 110 : _minimum(0), _iim(map), _comp(comp), _num() {} 110 111 111 112 /// \brief The number of items stored in the heap. 112 113 /// 113 114 /// Returns the number of items stored in the heap. 114 int size() const { return num_items; }115 int size() const { return _num; } 115 116 116 117 /// \brief Checks if the heap stores no items. 117 118 /// 118 119 /// Returns \c true if and only if the heap stores no items. 119 bool empty() const { return num_items==0; }120 bool empty() const { return _num==0; } 120 121 121 122 /// \brief Make empty this heap. … … 126 127 /// cross reference map for each item to \c PRE_HEAP. 127 128 void clear() { 128 container.clear(); minimum = 0; num_items= 0;129 _data.clear(); _minimum = 0; _num = 0; 129 130 } 130 131 … … 136 137 /// \ref increase(\c item, \c value) otherwise. 137 138 void set (const Item& item, const Prio& value) { 138 int i= iimap[item];139 if ( i >= 0 && container[i].in ) {140 if ( comp(value, container[i].prio) ) decrease(item, value);141 if ( comp(container[i].prio, value) ) increase(item, value);139 int i=_iim[item]; 140 if ( i >= 0 && _data[i].in ) { 141 if ( _comp(value, _data[i].prio) ) decrease(item, value); 142 if ( _comp(_data[i].prio, value) ) increase(item, value); 142 143 } else push(item, value); 143 144 } … … 148 149 /// \pre \c item must not be stored in the heap. 149 150 void push (const Item& item, const Prio& value) { 150 int i= iimap[item];151 int i=_iim[item]; 151 152 if ( i < 0 ) { 152 int s= container.size();153 iimap.set( item, s );154 store st;153 int s=_data.size(); 154 _iim.set( item, s ); 155 Store st; 155 156 st.name=item; 156 container.push_back(st);157 _data.push_back(st); 157 158 i=s; 158 159 } else { 159 container[i].parent=container[i].child=-1;160 container[i].degree=0;161 container[i].in=true;162 container[i].marked=false;163 } 164 165 if ( num_items) {166 container[container[minimum].right_neighbor].left_neighbor=i;167 container[i].right_neighbor=container[minimum].right_neighbor;168 container[minimum].right_neighbor=i;169 container[i].left_neighbor=minimum;170 if ( comp( value, container[minimum].prio) )minimum=i;160 _data[i].parent=_data[i].child=-1; 161 _data[i].degree=0; 162 _data[i].in=true; 163 _data[i].marked=false; 164 } 165 166 if ( _num ) { 167 _data[_data[_minimum].right_neighbor].left_neighbor=i; 168 _data[i].right_neighbor=_data[_minimum].right_neighbor; 169 _data[_minimum].right_neighbor=i; 170 _data[i].left_neighbor=_minimum; 171 if ( _comp( value, _data[_minimum].prio) ) _minimum=i; 171 172 } else { 172 container[i].right_neighbor=container[i].left_neighbor=i;173 minimum=i;174 } 175 container[i].prio=value;176 ++ num_items;173 _data[i].right_neighbor=_data[i].left_neighbor=i; 174 _minimum=i; 175 } 176 _data[i].prio=value; 177 ++_num; 177 178 } 178 179 … … 182 183 /// Compare. 183 184 /// \pre The heap must be nonempty. 184 Item top() const { return container[minimum].name; }185 Item top() const { return _data[_minimum].name; } 185 186 186 187 /// \brief Returns the minimum priority relative to \c Compare. … … 188 189 /// It returns the minimum priority relative to \c Compare. 189 190 /// \pre The heap must be nonempty. 190 const Prio& prio() const { return container[minimum].prio; }191 const Prio& prio() const { return _data[_minimum].prio; } 191 192 192 193 /// \brief Returns the priority of \c item. … … 195 196 /// \pre \c item must be in the heap. 196 197 const Prio& operator[](const Item& item) const { 197 return container[iimap[item]].prio;198 return _data[_iim[item]].prio; 198 199 } 199 200 … … 205 206 void pop() { 206 207 /*The first case is that there are only one root.*/ 207 if ( container[minimum].left_neighbor==minimum ) {208 container[minimum].in=false;209 if ( container[minimum].degree!=0 ) {210 makeroot( container[minimum].child);211 minimum=container[minimum].child;208 if ( _data[_minimum].left_neighbor==_minimum ) { 209 _data[_minimum].in=false; 210 if ( _data[_minimum].degree!=0 ) { 211 makeroot(_data[_minimum].child); 212 _minimum=_data[_minimum].child; 212 213 balance(); 213 214 } 214 215 } else { 215 int right= container[minimum].right_neighbor;216 unlace( minimum);217 container[minimum].in=false;218 if ( container[minimum].degree > 0 ) {219 int left= container[minimum].left_neighbor;220 int child= container[minimum].child;221 int last_child= container[child].left_neighbor;216 int right=_data[_minimum].right_neighbor; 217 unlace(_minimum); 218 _data[_minimum].in=false; 219 if ( _data[_minimum].degree > 0 ) { 220 int left=_data[_minimum].left_neighbor; 221 int child=_data[_minimum].child; 222 int last_child=_data[child].left_neighbor; 222 223 223 224 makeroot(child); 224 225 225 container[left].right_neighbor=child;226 container[child].left_neighbor=left;227 container[right].left_neighbor=last_child;228 container[last_child].right_neighbor=right;229 } 230 minimum=right;226 _data[left].right_neighbor=child; 227 _data[child].left_neighbor=left; 228 _data[right].left_neighbor=last_child; 229 _data[last_child].right_neighbor=right; 230 } 231 _minimum=right; 231 232 balance(); 232 233 } // the case where there are more roots 233 -- num_items;234 --_num; 234 235 } 235 236 … … 239 240 /// stored in the heap. It is quite inefficient in Fibonacci heaps. 240 241 void erase (const Item& item) { 241 int i= iimap[item];242 243 if ( i >= 0 && container[i].in ) {244 if ( container[i].parent!=-1 ) {245 int p= container[i].parent;242 int i=_iim[item]; 243 244 if ( i >= 0 && _data[i].in ) { 245 if ( _data[i].parent!=-1 ) { 246 int p=_data[i].parent; 246 247 cut(i,p); 247 248 cascade(p); 248 249 } 249 minimum=i; //As if its prio would be -infinity250 _minimum=i; //As if its prio would be -infinity 250 251 pop(); 251 252 } … … 258 259 /// value relative to \c Compare. 259 260 void decrease (Item item, const Prio& value) { 260 int i= iimap[item];261 container[i].prio=value;262 int p= container[i].parent;263 264 if ( p!=-1 && comp(value, container[p].prio) ) {261 int i=_iim[item]; 262 _data[i].prio=value; 263 int p=_data[i].parent; 264 265 if ( p!=-1 && _comp(value, _data[p].prio) ) { 265 266 cut(i,p); 266 267 cascade(p); 267 268 } 268 if ( comp(value, container[minimum].prio) )minimum=i;269 if ( _comp(value, _data[_minimum].prio) ) _minimum=i; 269 270 } 270 271 … … 290 291 /// get back to the heap again. 291 292 State state(const Item &item) const { 292 int i= iimap[item];293 int i=_iim[item]; 293 294 if( i>=0 ) { 294 if ( container[i].in ) i=0;295 if ( _data[i].in ) i=0; 295 296 else i=-2; 296 297 } … … 302 303 /// Sets the state of the \c item in the heap. It can be used to 303 304 /// manually clear the heap when it is important to achive the 304 /// better time complexity.305 /// better time _complexity. 305 306 /// \param i The item. 306 307 /// \param st The state. It should not be \c IN_HEAP. … … 312 313 erase(i); 313 314 } 314 iimap[i] = st;315 _iim[i] = st; 315 316 break; 316 317 case IN_HEAP: … … 323 324 void balance() { 324 325 325 int maxdeg=int( std::floor( 2.08*log(double( container.size()))))+1;326 int maxdeg=int( std::floor( 2.08*log(double(_data.size()))))+1; 326 327 327 328 std::vector<int> A(maxdeg,-1); … … 331 332 *We set minimum to this during balance(). 332 333 */ 333 int anchor= container[minimum].left_neighbor;334 int next= minimum;334 int anchor=_data[_minimum].left_neighbor; 335 int next=_minimum; 335 336 bool end=false; 336 337 … … 338 339 int active=next; 339 340 if ( anchor==active ) end=true; 340 int d= container[active].degree;341 next= container[active].right_neighbor;341 int d=_data[active].degree; 342 next=_data[active].right_neighbor; 342 343 343 344 while (A[d]!=-1) { 344 if( comp(container[active].prio, container[A[d]].prio) ) {345 if( _comp(_data[active].prio, _data[A[d]].prio) ) { 345 346 fuse(active,A[d]); 346 347 } else { … … 355 356 356 357 357 while ( container[minimum].parent >=0 )358 minimum=container[minimum].parent;359 int s= minimum;360 int m= minimum;358 while ( _data[_minimum].parent >=0 ) 359 _minimum=_data[_minimum].parent; 360 int s=_minimum; 361 int m=_minimum; 361 362 do { 362 if ( comp(container[s].prio, container[minimum].prio) )minimum=s;363 s= container[s].right_neighbor;363 if ( _comp(_data[s].prio, _data[_minimum].prio) ) _minimum=s; 364 s=_data[s].right_neighbor; 364 365 } while ( s != m ); 365 366 } … … 368 369 int s=c; 369 370 do { 370 container[s].parent=-1;371 s= container[s].right_neighbor;371 _data[s].parent=-1; 372 s=_data[s].right_neighbor; 372 373 } while ( s != c ); 373 374 } … … 377 378 *Replacing a from the children of b. 378 379 */ 379 -- container[b].degree;380 381 if ( container[b].degree !=0 ) {382 int child= container[b].child;380 --_data[b].degree; 381 382 if ( _data[b].degree !=0 ) { 383 int child=_data[b].child; 383 384 if ( child==a ) 384 container[b].child=container[child].right_neighbor;385 _data[b].child=_data[child].right_neighbor; 385 386 unlace(a); 386 387 } … … 388 389 389 390 /*Lacing a to the roots.*/ 390 int right= container[minimum].right_neighbor;391 container[minimum].right_neighbor=a;392 container[a].left_neighbor=minimum;393 container[a].right_neighbor=right;394 container[right].left_neighbor=a;395 396 container[a].parent=-1;397 container[a].marked=false;391 int right=_data[_minimum].right_neighbor; 392 _data[_minimum].right_neighbor=a; 393 _data[a].left_neighbor=_minimum; 394 _data[a].right_neighbor=right; 395 _data[right].left_neighbor=a; 396 397 _data[a].parent=-1; 398 _data[a].marked=false; 398 399 } 399 400 400 401 void cascade(int a) { 401 if ( container[a].parent!=-1 ) {402 int p= container[a].parent;403 404 if ( container[a].marked==false ) container[a].marked=true;402 if ( _data[a].parent!=-1 ) { 403 int p=_data[a].parent; 404 405 if ( _data[a].marked==false ) _data[a].marked=true; 405 406 else { 406 407 cut(a,p); … … 414 415 415 416 /*Lacing b under a.*/ 416 container[b].parent=a;417 418 if ( container[a].degree==0) {419 container[b].left_neighbor=b;420 container[b].right_neighbor=b;421 container[a].child=b;417 _data[b].parent=a; 418 419 if (_data[a].degree==0) { 420 _data[b].left_neighbor=b; 421 _data[b].right_neighbor=b; 422 _data[a].child=b; 422 423 } else { 423 int child= container[a].child;424 int last_child= container[child].left_neighbor;425 container[child].left_neighbor=b;426 container[b].right_neighbor=child;427 container[last_child].right_neighbor=b;428 container[b].left_neighbor=last_child;429 } 430 431 ++ container[a].degree;432 433 container[b].marked=false;424 int child=_data[a].child; 425 int last_child=_data[child].left_neighbor; 426 _data[child].left_neighbor=b; 427 _data[b].right_neighbor=child; 428 _data[last_child].right_neighbor=b; 429 _data[b].left_neighbor=last_child; 430 } 431 432 ++_data[a].degree; 433 434 _data[b].marked=false; 434 435 } 435 436 … … 438 439 */ 439 440 void unlace(int a) { 440 int leftn= container[a].left_neighbor;441 int rightn= container[a].right_neighbor;442 container[leftn].right_neighbor=rightn;443 container[rightn].left_neighbor=leftn;444 } 445 446 447 class store {441 int leftn=_data[a].left_neighbor; 442 int rightn=_data[a].right_neighbor; 443 _data[leftn].right_neighbor=rightn; 444 _data[rightn].left_neighbor=leftn; 445 } 446 447 448 class Store { 448 449 friend class FibHeap; 449 450 … … 458 459 Prio prio; 459 460 460 store() : parent(-1), child(-1), degree(), marked(false), in(true) {}461 Store() : parent(-1), child(-1), degree(), marked(false), in(true) {} 461 462 }; 462 463 };
Note: See TracChangeset
for help on using the changeset viewer.