Changeset 703:bb3392fe91f2 in lemon-main
- Timestamp:
- 07/09/09 04:07:08 (16 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon
- Files:
-
- 4 edited
-
binom_heap.h (modified) (11 diffs)
-
fourary_heap.h (modified) (9 diffs)
-
kary_heap.h (modified) (7 diffs)
-
pairing_heap.h (modified) (11 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/binom_heap.h
r701 r703 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 21 21 22 22 ///\file 23 ///\ingroup auxdat23 ///\ingroup heaps 24 24 ///\brief Binomial Heap implementation. 25 25 26 26 #include <vector> 27 #include <utility> 27 28 #include <functional> 28 29 #include <lemon/math.h> … … 31 32 namespace lemon { 32 33 33 /// \ingroup auxdat34 /// \ingroup heaps 34 35 /// 35 ///\brief Binomial Heap.36 ///\brief Binomial heap data structure. 36 37 /// 37 ///This class implements the \e Binomial \e heap data structure. A \e heap 38 ///is a data structure for storing items with specified values called \e 39 ///priorities in such a way that finding the item with minimum priority is 40 ///efficient. \c Compare specifies the ordering of the priorities. In a heap 41 ///one can change the priority of an item, add or erase an item, etc. 38 /// This class implements the \e binomial \e heap data structure. 39 /// It fully conforms to the \ref concepts::Heap "heap concept". 42 40 /// 43 ///The methods \ref increase and \ref erase are not efficient in a Binomial 44 ///heap. In case of many calls to these operations, it is better to use a 45 ///\ref BinHeap "binary heap". 41 /// The methods \ref increase() and \ref erase() are not efficient 42 /// in a binomial heap. In case of many calls of these operations, 43 /// it is better to use other heap structure, e.g. \ref BinHeap 44 /// "binary heap". 46 45 /// 47 ///\param _Prio Type of the priority of the items. 48 ///\param _ItemIntMap A read and writable Item int map, used internally 49 ///to handle the cross references. 50 ///\param _Compare A class for the ordering of the priorities. The 51 ///default is \c std::less<_Prio>. 52 /// 53 ///\sa BinHeap 54 ///\sa Dijkstra 55 ///\author Dorian Batha 56 46 /// \tparam PR Type of the priorities of the items. 47 /// \tparam IM A read-writable item map with \c int values, used 48 /// internally to handle the cross references. 49 /// \tparam CMP A functor class for comparing the priorities. 50 /// The default is \c std::less<PR>. 57 51 #ifdef DOXYGEN 58 template <typename _Prio, 59 typename _ItemIntMap, 60 typename _Compare> 52 template <typename PR, typename IM, typename CMP> 61 53 #else 62 template <typename _Prio, 63 typename _ItemIntMap, 64 typename _Compare = std::less<_Prio> > 54 template <typename PR, typename IM, typename CMP = std::less<PR> > 65 55 #endif 66 56 class BinomHeap { 67 57 public: 68 typedef _ItemIntMap ItemIntMap; 69 typedef _Prio Prio; 58 /// Type of the item-int map. 59 typedef IM ItemIntMap; 60 /// Type of the priorities. 61 typedef PR Prio; 62 /// Type of the items stored in the heap. 70 63 typedef typename ItemIntMap::Key Item; 71 typedef std::pair<Item,Prio> Pair; 72 typedef _Compare Compare; 64 /// Functor type for comparing the priorities. 65 typedef CMP Compare; 66 67 /// \brief Type to represent the states of the items. 68 /// 69 /// Each item has a state associated to it. It can be "in heap", 70 /// "pre-heap" or "post-heap". The latter two are indifferent from the 71 /// heap's point of view, but may be useful to the user. 72 /// 73 /// The item-int map must be initialized in such way that it assigns 74 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 75 enum State { 76 IN_HEAP = 0, ///< = 0. 77 PRE_HEAP = -1, ///< = -1. 78 POST_HEAP = -2 ///< = -2. 79 }; 73 80 74 81 private: 75 82 class store; 76 83 77 std::vector<store> container;78 int minimum,head;79 ItemIntMap & iimap;80 Compare comp;81 int num_items;84 std::vector<store> _data; 85 int _min, _head; 86 ItemIntMap &_iim; 87 Compare _comp; 88 int _num_items; 82 89 83 90 public: 84 ///Status of the nodes 85 enum State { 86 ///The node is in the heap 87 IN_HEAP = 0, 88 ///The node has never been in the heap 89 PRE_HEAP = -1, 90 ///The node was in the heap but it got out of it 91 POST_HEAP = -2 92 }; 93 94 /// \brief The constructor 95 /// 96 /// \c _iimap should be given to the constructor, since it is 97 /// used internally to handle the cross references. 98 explicit BinomHeap(ItemIntMap &_iimap) 99 : minimum(0), head(-1), iimap(_iimap), num_items() {} 100 101 /// \brief The constructor 102 /// 103 /// \c _iimap should be given to the constructor, since it is used 104 /// internally to handle the cross references. \c _comp is an 105 /// object for ordering of the priorities. 106 BinomHeap(ItemIntMap &_iimap, const Compare &_comp) 107 : minimum(0), head(-1), iimap(_iimap), comp(_comp), num_items() {} 91 /// \brief Constructor. 92 /// 93 /// Constructor. 94 /// \param map A map that assigns \c int values to the items. 95 /// It is used internally to handle the cross references. 96 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 97 explicit BinomHeap(ItemIntMap &map) 98 : _min(0), _head(-1), _iim(map), _num_items(0) {} 99 100 /// \brief Constructor. 101 /// 102 /// Constructor. 103 /// \param map A map that assigns \c int values to the items. 104 /// It is used internally to handle the cross references. 105 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 106 /// \param comp The function object used for comparing the priorities. 107 BinomHeap(ItemIntMap &map, const Compare &comp) 108 : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {} 108 109 109 110 /// \brief The number of items stored in the heap. 110 111 /// 111 /// Returns the number of items stored in the heap. 112 int size() const { return num_items; } 113 114 /// \brief Checks if the heap stores no items. 115 /// 116 /// Returns \c true if and only if the heap stores no items. 117 bool empty() const { return num_items==0; } 118 119 /// \brief Make empty this heap. 120 /// 121 /// Make empty this heap. It does not change the cross reference 122 /// map. If you want to reuse a heap what is not surely empty you 123 /// should first clear the heap and after that you should set the 124 /// cross reference map for each item to \c PRE_HEAP. 112 /// This function returns the number of items stored in the heap. 113 int size() const { return _num_items; } 114 115 /// \brief Check if the heap is empty. 116 /// 117 /// This function returns \c true if the heap is empty. 118 bool empty() const { return _num_items==0; } 119 120 /// \brief Make the heap empty. 121 /// 122 /// This functon makes the heap empty. 123 /// It does not change the cross reference map. If you want to reuse 124 /// a heap that is not surely empty, you should first clear it and 125 /// then you should set the cross reference map to \c PRE_HEAP 126 /// for each item. 125 127 void clear() { 126 container.clear(); minimum=0; num_items=0; head=-1; 127 } 128 129 /// \brief \c item gets to the heap with priority \c value independently 130 /// if \c item was already there. 131 /// 132 /// This method calls \ref push(\c item, \c value) if \c item is not 133 /// stored in the heap and it calls \ref decrease(\c item, \c value) or 134 /// \ref increase(\c item, \c value) otherwise. 128 _data.clear(); _min=0; _num_items=0; _head=-1; 129 } 130 131 /// \brief Set the priority of an item or insert it, if it is 132 /// not stored in the heap. 133 /// 134 /// This method sets the priority of the given item if it is 135 /// already stored in the heap. Otherwise it inserts the given 136 /// item into the heap with the given priority. 137 /// \param item The item. 138 /// \param value The priority. 135 139 void set (const Item& item, const Prio& value) { 136 int i= iimap[item];137 if ( i >= 0 && container[i].in ) {138 if ( comp(value, container[i].prio) ) decrease(item, value);139 if ( comp(container[i].prio, value) ) increase(item, value);140 int i=_iim[item]; 141 if ( i >= 0 && _data[i].in ) { 142 if ( _comp(value, _data[i].prio) ) decrease(item, value); 143 if ( _comp(_data[i].prio, value) ) increase(item, value); 140 144 } else push(item, value); 141 145 } 142 146 143 /// \brief Adds \c item to the heap with priority \c value. 144 /// 145 /// Adds \c item to the heap with priority \c value. 146 /// \pre \c item must not be stored in the heap. 147 /// \brief Insert an item into the heap with the given priority. 148 /// 149 /// This function inserts the given item into the heap with the 150 /// given priority. 151 /// \param item The item to insert. 152 /// \param value The priority of the item. 153 /// \pre \e item must not be stored in the heap. 147 154 void push (const Item& item, const Prio& value) { 148 int i= iimap[item];155 int i=_iim[item]; 149 156 if ( i<0 ) { 150 int s= container.size();151 iimap.set( item,s );157 int s=_data.size(); 158 _iim.set( item,s ); 152 159 store st; 153 160 st.name=item; 154 container.push_back(st);161 _data.push_back(st); 155 162 i=s; 156 163 } 157 164 else { 158 container[i].parent=container[i].right_neighbor=container[i].child=-1;159 container[i].degree=0;160 container[i].in=true;161 } 162 container[i].prio=value;163 164 if( 0== num_items ) { head=i; minimum=i; }165 _data[i].parent=_data[i].right_neighbor=_data[i].child=-1; 166 _data[i].degree=0; 167 _data[i].in=true; 168 } 169 _data[i].prio=value; 170 171 if( 0==_num_items ) { _head=i; _min=i; } 165 172 else { merge(i); } 166 173 167 minimum = find_min();168 169 ++ num_items;170 } 171 172 /// \brief Return s the item with minimum priority relative to \c Compare.173 /// 174 /// This method returns the item with minimum priority relative to \c175 /// Compare.176 /// \pre The heap must be nonempty.177 Item top() const { return container[minimum].name; } 178 179 /// \brief Returns the minimum priority relative to \c Compare.180 /// 181 /// It returns the minimum priority relative to \c Compare.182 /// \pre The heap must be nonempty.183 const Prio& prio() const { return container[minimum].prio; } 184 185 /// \brief Returns the priority of \c item.186 /// 187 /// It returns the priority of \citem.188 /// \pre \ citem must be in the heap.174 _min = findMin(); 175 176 ++_num_items; 177 } 178 179 /// \brief Return the item having minimum priority. 180 /// 181 /// This function returns the item having minimum priority. 182 /// \pre The heap must be non-empty. 183 Item top() const { return _data[_min].name; } 184 185 /// \brief The minimum priority. 186 /// 187 /// This function returns the minimum priority. 188 /// \pre The heap must be non-empty. 189 Prio prio() const { return _data[_min].prio; } 190 191 /// \brief The priority of the given item. 192 /// 193 /// This function returns the priority of the given item. 194 /// \param item The item. 195 /// \pre \e item must be in the heap. 189 196 const Prio& operator[](const Item& item) const { 190 return container[iimap[item]].prio; 191 } 192 193 /// \brief Deletes the item with minimum priority relative to \c Compare. 194 /// 195 /// This method deletes the item with minimum priority relative to \c 196 /// Compare from the heap. 197 return _data[_iim[item]].prio; 198 } 199 200 /// \brief Remove the item having minimum priority. 201 /// 202 /// This function removes the item having minimum priority. 197 203 /// \pre The heap must be non-empty. 198 204 void pop() { 199 container[minimum].in=false;205 _data[_min].in=false; 200 206 201 207 int head_child=-1; 202 if ( container[minimum].child!=-1 ) {203 int child= container[minimum].child;208 if ( _data[_min].child!=-1 ) { 209 int child=_data[_min].child; 204 210 int neighb; 205 211 int prev=-1; 206 212 while( child!=-1 ) { 207 neighb= container[child].right_neighbor;208 container[child].parent=-1;209 container[child].right_neighbor=prev;213 neighb=_data[child].right_neighbor; 214 _data[child].parent=-1; 215 _data[child].right_neighbor=prev; 210 216 head_child=child; 211 217 prev=child; … … 215 221 216 222 // The first case is that there are only one root. 217 if ( -1== container[head].right_neighbor ) {218 head=head_child;223 if ( -1==_data[_head].right_neighbor ) { 224 _head=head_child; 219 225 } 220 226 // The case where there are more roots. 221 227 else { 222 if( head!=minimum ) { unlace(minimum); }223 else { head=container[head].right_neighbor; }228 if( _head!=_min ) { unlace(_min); } 229 else { _head=_data[_head].right_neighbor; } 224 230 225 231 merge(head_child); 226 232 } 227 minimum=find_min(); 228 --num_items; 229 } 230 231 /// \brief Deletes \c item from the heap. 232 /// 233 /// This method deletes \c item from the heap, if \c item was already 234 /// stored in the heap. It is quite inefficient in Binomial heaps. 233 _min=findMin(); 234 --_num_items; 235 } 236 237 /// \brief Remove the given item from the heap. 238 /// 239 /// This function removes the given item from the heap if it is 240 /// already stored. 241 /// \param item The item to delete. 242 /// \pre \e item must be in the heap. 235 243 void erase (const Item& item) { 236 int i= iimap[item];237 if ( i >= 0 && container[i].in ) {238 decrease( item, container[minimum].prio-1 );244 int i=_iim[item]; 245 if ( i >= 0 && _data[i].in ) { 246 decrease( item, _data[_min].prio-1 ); 239 247 pop(); 240 248 } 241 249 } 242 250 243 /// \brief Decreases the priority of \c item to \c value. 244 /// 245 /// This method decreases the priority of \c item to \c value. 246 /// \pre \c item must be stored in the heap with priority at least \c 247 /// value relative to \c Compare. 251 /// \brief Decrease the priority of an item to the given value. 252 /// 253 /// This function decreases the priority of an item to the given value. 254 /// \param item The item. 255 /// \param value The priority. 256 /// \pre \e item must be stored in the heap with priority at least \e value. 248 257 void decrease (Item item, const Prio& value) { 249 int i= iimap[item];250 251 if( comp( value,container[i].prio ) ) {252 container[i].prio=value;253 254 int p_loc= container[i].parent, loc=i;258 int i=_iim[item]; 259 260 if( _comp( value,_data[i].prio ) ) { 261 _data[i].prio=value; 262 263 int p_loc=_data[i].parent, loc=i; 255 264 int parent, child, neighb; 256 265 257 while( -1!=p_loc && comp(container[loc].prio,container[p_loc].prio) ) {266 while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) { 258 267 259 268 // parent set for other loc_child 260 child= container[loc].child;269 child=_data[loc].child; 261 270 while( -1!=child ) { 262 container[child].parent=p_loc;263 child= container[child].right_neighbor;271 _data[child].parent=p_loc; 272 child=_data[child].right_neighbor; 264 273 } 265 274 266 275 // parent set for other p_loc_child 267 child= container[p_loc].child;276 child=_data[p_loc].child; 268 277 while( -1!=child ) { 269 container[child].parent=loc;270 child= container[child].right_neighbor;271 } 272 273 child= container[p_loc].child;274 container[p_loc].child=container[loc].child;278 _data[child].parent=loc; 279 child=_data[child].right_neighbor; 280 } 281 282 child=_data[p_loc].child; 283 _data[p_loc].child=_data[loc].child; 275 284 if( child==loc ) 276 285 child=p_loc; 277 container[loc].child=child;286 _data[loc].child=child; 278 287 279 288 // left_neighb set for p_loc 280 if( container[loc].child!=p_loc ) {281 while( container[child].right_neighbor!=loc )282 child= container[child].right_neighbor;283 container[child].right_neighbor=p_loc;289 if( _data[loc].child!=p_loc ) { 290 while( _data[child].right_neighbor!=loc ) 291 child=_data[child].right_neighbor; 292 _data[child].right_neighbor=p_loc; 284 293 } 285 294 286 295 // left_neighb set for loc 287 parent= container[p_loc].parent;288 if( -1!=parent ) child= container[parent].child;289 else child= head;296 parent=_data[p_loc].parent; 297 if( -1!=parent ) child=_data[parent].child; 298 else child=_head; 290 299 291 300 if( child!=p_loc ) { 292 while( container[child].right_neighbor!=p_loc )293 child= container[child].right_neighbor;294 container[child].right_neighbor=loc;295 } 296 297 neighb= container[p_loc].right_neighbor;298 container[p_loc].right_neighbor=container[loc].right_neighbor;299 container[loc].right_neighbor=neighb;300 301 container[p_loc].parent=loc;302 container[loc].parent=parent;303 304 if( -1!=parent && container[parent].child==p_loc )305 container[parent].child=loc;301 while( _data[child].right_neighbor!=p_loc ) 302 child=_data[child].right_neighbor; 303 _data[child].right_neighbor=loc; 304 } 305 306 neighb=_data[p_loc].right_neighbor; 307 _data[p_loc].right_neighbor=_data[loc].right_neighbor; 308 _data[loc].right_neighbor=neighb; 309 310 _data[p_loc].parent=loc; 311 _data[loc].parent=parent; 312 313 if( -1!=parent && _data[parent].child==p_loc ) 314 _data[parent].child=loc; 306 315 307 316 /*if new parent will be the first root*/ 308 if( head==p_loc ) 309 head=loc; 310 311 p_loc=container[loc].parent; 312 } 313 } 314 if( comp(value,container[minimum].prio) ) { 315 minimum=i; 316 } 317 } 318 319 /// \brief Increases the priority of \c item to \c value. 320 /// 321 /// This method sets the priority of \c item to \c value. Though 322 /// there is no precondition on the priority of \c item, this 323 /// method should be used only if it is indeed necessary to increase 324 /// (relative to \c Compare) the priority of \c item, because this 325 /// method is inefficient. 317 if( _head==p_loc ) 318 _head=loc; 319 320 p_loc=_data[loc].parent; 321 } 322 } 323 if( _comp(value,_data[_min].prio) ) { 324 _min=i; 325 } 326 } 327 328 /// \brief Increase the priority of an item to the given value. 329 /// 330 /// This function increases the priority of an item to the given value. 331 /// \param item The item. 332 /// \param value The priority. 333 /// \pre \e item must be stored in the heap with priority at most \e value. 326 334 void increase (Item item, const Prio& value) { 327 335 erase(item); … … 329 337 } 330 338 331 332 /// \brief Returns if \c item is in, has already been in, or has never333 /// been in the heap.334 /// 335 /// This method returns PRE_HEAP if \c item has never been in the336 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP337 /// otherwise. In the latter case it is possible that \c item will338 /// get back to the heap again.339 /// \brief Return the state of an item. 340 /// 341 /// This method returns \c PRE_HEAP if the given item has never 342 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 343 /// and \c POST_HEAP otherwise. 344 /// In the latter case it is possible that the item will get back 345 /// to the heap again. 346 /// \param item The item. 339 347 State state(const Item &item) const { 340 int i= iimap[item];348 int i=_iim[item]; 341 349 if( i>=0 ) { 342 if ( container[i].in ) i=0;350 if ( _data[i].in ) i=0; 343 351 else i=-2; 344 352 } … … 346 354 } 347 355 348 /// \brief Set s the state of the \citem in the heap.349 /// 350 /// Sets the state of the \c item in the heap. It can be used to351 /// manually clear the heap when it is important to achive the352 /// better time complexity.356 /// \brief Set the state of an item in the heap. 357 /// 358 /// This function sets the state of the given item in the heap. 359 /// It can be used to manually clear the heap when it is important 360 /// to achive better time complexity. 353 361 /// \param i The item. 354 362 /// \param st The state. It should not be \c IN_HEAP. … … 360 368 erase(i); 361 369 } 362 iimap[i] = st;370 _iim[i] = st; 363 371 break; 364 372 case IN_HEAP: … … 368 376 369 377 private: 370 int find _min() {378 int findMin() { 371 379 int min_loc=-1, min_val; 372 int x= head;380 int x=_head; 373 381 if( x!=-1 ) { 374 min_val= container[x].prio;382 min_val=_data[x].prio; 375 383 min_loc=x; 376 x= container[x].right_neighbor;384 x=_data[x].right_neighbor; 377 385 378 386 while( x!=-1 ) { 379 if( comp( container[x].prio,min_val ) ) {380 min_val= container[x].prio;387 if( _comp( _data[x].prio,min_val ) ) { 388 min_val=_data[x].prio; 381 389 min_loc=x; 382 390 } 383 x= container[x].right_neighbor;391 x=_data[x].right_neighbor; 384 392 } 385 393 } … … 390 398 interleave(a); 391 399 392 int x= head;400 int x=_head; 393 401 if( -1!=x ) { 394 int x_prev=-1, x_next= container[x].right_neighbor;402 int x_prev=-1, x_next=_data[x].right_neighbor; 395 403 while( -1!=x_next ) { 396 if( container[x].degree!=container[x_next].degree || ( -1!=container[x_next].right_neighbor && container[container[x_next].right_neighbor].degree==container[x].degree ) ) {404 if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) { 397 405 x_prev=x; 398 406 x=x_next; 399 407 } 400 408 else { 401 if( comp(container[x].prio,container[x_next].prio) ) {402 container[x].right_neighbor=container[x_next].right_neighbor;409 if( _comp(_data[x].prio,_data[x_next].prio) ) { 410 _data[x].right_neighbor=_data[x_next].right_neighbor; 403 411 fuse(x_next,x); 404 412 } 405 413 else { 406 if( -1==x_prev ) { head=x_next; }414 if( -1==x_prev ) { _head=x_next; } 407 415 else { 408 container[x_prev].right_neighbor=x_next;416 _data[x_prev].right_neighbor=x_next; 409 417 } 410 418 fuse(x,x_next); … … 412 420 } 413 421 } 414 x_next= container[x].right_neighbor;422 x_next=_data[x].right_neighbor; 415 423 } 416 424 } … … 420 428 int other=-1, head_other=-1; 421 429 422 while( -1!=a || -1!= head ) {430 while( -1!=a || -1!=_head ) { 423 431 if( -1==a ) { 424 432 if( -1==head_other ) { 425 head_other= head;433 head_other=_head; 426 434 } 427 435 else { 428 container[other].right_neighbor=head;429 } 430 head=-1;431 } 432 else if( -1== head ) {436 _data[other].right_neighbor=_head; 437 } 438 _head=-1; 439 } 440 else if( -1==_head ) { 433 441 if( -1==head_other ) { 434 442 head_other=a; 435 443 } 436 444 else { 437 container[other].right_neighbor=a;445 _data[other].right_neighbor=a; 438 446 } 439 447 a=-1; 440 448 } 441 449 else { 442 if( container[a].degree<container[head].degree ) {450 if( _data[a].degree<_data[_head].degree ) { 443 451 if( -1==head_other ) { 444 452 head_other=a; 445 453 } 446 454 else { 447 container[other].right_neighbor=a;455 _data[other].right_neighbor=a; 448 456 } 449 457 other=a; 450 a= container[a].right_neighbor;458 a=_data[a].right_neighbor; 451 459 } 452 460 else { 453 461 if( -1==head_other ) { 454 head_other= head;462 head_other=_head; 455 463 } 456 464 else { 457 container[other].right_neighbor=head;465 _data[other].right_neighbor=_head; 458 466 } 459 other= head;460 head=container[head].right_neighbor;461 } 462 } 463 } 464 head=head_other;467 other=_head; 468 _head=_data[_head].right_neighbor; 469 } 470 } 471 } 472 _head=head_other; 465 473 } 466 474 467 475 // Lacing a under b 468 476 void fuse(int a, int b) { 469 container[a].parent=b;470 container[a].right_neighbor=container[b].child;471 container[b].child=a;472 473 ++ container[b].degree;477 _data[a].parent=b; 478 _data[a].right_neighbor=_data[b].child; 479 _data[b].child=a; 480 481 ++_data[b].degree; 474 482 } 475 483 476 484 // It is invoked only if a has siblings. 477 485 void unlace(int a) { 478 int neighb= container[a].right_neighbor;479 int other= head;480 481 while( container[other].right_neighbor!=a )482 other= container[other].right_neighbor;483 container[other].right_neighbor=neighb;486 int neighb=_data[a].right_neighbor; 487 int other=_head; 488 489 while( _data[other].right_neighbor!=a ) 490 other=_data[other].right_neighbor; 491 _data[other].right_neighbor=neighb; 484 492 } 485 493 -
lemon/fourary_heap.h
r701 r703 1 /* -*- C++-*-2 * 3 * This file is a part of LEMON, a generic C++ optimization library 4 * 5 * Copyright (C) 2003-200 81 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 * 5 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 20 20 #define LEMON_FOURARY_HEAP_H 21 21 22 ///\ingroup auxdat22 ///\ingroup heaps 23 23 ///\file 24 ///\brief 4ary Heap implementation. 25 26 #include <iostream> 24 ///\brief Fourary heap implementation. 25 27 26 #include <vector> 28 27 #include <utility> … … 31 30 namespace lemon { 32 31 33 ///\ingroup auxdat 34 /// 35 ///\brief A 4ary Heap implementation. 36 /// 37 ///This class implements the \e 4ary \e heap data structure. A \e heap 38 ///is a data structure for storing items with specified values called \e 39 ///priorities in such a way that finding the item with minimum priority is 40 ///efficient. \c Compare specifies the ordering of the priorities. In a heap 41 ///one can change the priority of an item, add or erase an item, etc. 42 /// 43 ///\param _Prio Type of the priority of the items. 44 ///\param _ItemIntMap A read and writable Item int map, used internally 45 ///to handle the cross references. 46 ///\param _Compare A class for the ordering of the priorities. The 47 ///default is \c std::less<_Prio>. 48 /// 49 ///\sa FibHeap 50 ///\sa Dijkstra 51 ///\author Dorian Batha 52 53 template <typename _Prio, typename _ItemIntMap, 54 typename _Compare = std::less<_Prio> > 55 32 /// \ingroup heaps 33 /// 34 ///\brief Fourary heap data structure. 35 /// 36 /// This class implements the \e fourary \e heap data structure. 37 /// It fully conforms to the \ref concepts::Heap "heap concept". 38 /// 39 /// The fourary heap is a specialization of the \ref KaryHeap "K-ary heap" 40 /// for <tt>K=4</tt>. It is similar to the \ref BinHeap "binary heap", 41 /// but its nodes have at most four children, instead of two. 42 /// 43 /// \tparam PR Type of the priorities of the items. 44 /// \tparam IM A read-writable item map with \c int values, used 45 /// internally to handle the cross references. 46 /// \tparam CMP A functor class for comparing the priorities. 47 /// The default is \c std::less<PR>. 48 /// 49 ///\sa BinHeap 50 ///\sa KaryHeap 51 #ifdef DOXYGEN 52 template <typename PR, typename IM, typename CMP> 53 #else 54 template <typename PR, typename IM, typename CMP = std::less<PR> > 55 #endif 56 56 class FouraryHeap { 57 58 57 public: 59 /// \e60 typedef _ItemIntMapItemIntMap;61 /// \e62 typedef _PrioPrio;63 /// \e58 /// Type of the item-int map. 59 typedef IM ItemIntMap; 60 /// Type of the priorities. 61 typedef PR Prio; 62 /// Type of the items stored in the heap. 64 63 typedef typename ItemIntMap::Key Item; 65 /// \e64 /// Type of the item-priority pairs. 66 65 typedef std::pair<Item,Prio> Pair; 67 /// \e68 typedef _CompareCompare;69 70 /// \brief Type to represent the items states.71 /// 72 /// Each Item element have a state associated to it. It maybe "in heap",73 /// "pre heap" or "postheap". The latter two are indifferent from the66 /// Functor type for comparing the priorities. 67 typedef CMP Compare; 68 69 /// \brief Type to represent the states of the items. 70 /// 71 /// Each item has a state associated to it. It can be "in heap", 72 /// "pre-heap" or "post-heap". The latter two are indifferent from the 74 73 /// heap's point of view, but may be useful to the user. 75 74 /// 76 /// The ItemIntMap \e should be initialized in such way that it maps77 /// PRE_HEAP (-1) to any element to be put in the heap...75 /// The item-int map must be initialized in such way that it assigns 76 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 78 77 enum State { 79 IN_HEAP = 0, 80 PRE_HEAP = -1, 81 POST_HEAP = -2 78 IN_HEAP = 0, ///< = 0. 79 PRE_HEAP = -1, ///< = -1. 80 POST_HEAP = -2 ///< = -2. 82 81 }; 83 82 84 83 private: 85 std::vector<Pair> data;86 Compare comp;87 ItemIntMap & iim;84 std::vector<Pair> _data; 85 Compare _comp; 86 ItemIntMap &_iim; 88 87 89 88 public: 90 /// \brief The constructor.91 /// 92 /// The constructor.93 /// \param _iim should be given to the constructor, since it is used94 /// internally to handle the cross references. The value of the map95 /// should be PRE_HEAP (-1) for each element.96 explicit FouraryHeap(ItemIntMap & _iim) : iim(_iim) {}97 98 /// \brief The constructor.99 /// 100 /// The constructor.101 /// \param _iim should be given to the constructor, since it is used102 /// internally to handle the cross references. The value of the map103 /// should be PRE_HEAP (-1) for each element.104 /// 105 /// \param _comp The comparator function object.106 FouraryHeap(ItemIntMap &_iim, const Compare &_comp)107 : iim(_iim), comp(_comp) {} 108 109 /// The number of items stored in the heap.110 /// 111 /// \brief Returns the number of items stored in the heap.112 int size() const { return data.size(); } 113 114 /// \brief Checks if the heap stores no items.115 /// 116 /// Returns \c true if and only if the heap stores no items.117 bool empty() const { return data.empty(); } 118 119 /// \brief Make empty this heap.120 /// 121 /// Make empty this heap. It does not change the cross reference map.122 /// If you want to reuse what is not surely empty you should first clear123 /// the heap and after that you should set the cross reference map for124 /// each item to \c PRE_HEAP.125 void clear() { data.clear(); }89 /// \brief Constructor. 90 /// 91 /// Constructor. 92 /// \param map A map that assigns \c int values to the items. 93 /// It is used internally to handle the cross references. 94 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 95 explicit FouraryHeap(ItemIntMap &map) : _iim(map) {} 96 97 /// \brief Constructor. 98 /// 99 /// Constructor. 100 /// \param map A map that assigns \c int values to the items. 101 /// It is used internally to handle the cross references. 102 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 103 /// \param comp The function object used for comparing the priorities. 104 FouraryHeap(ItemIntMap &map, const Compare &comp) 105 : _iim(map), _comp(comp) {} 106 107 /// \brief The number of items stored in the heap. 108 /// 109 /// This function returns the number of items stored in the heap. 110 int size() const { return _data.size(); } 111 112 /// \brief Check if the heap is empty. 113 /// 114 /// This function returns \c true if the heap is empty. 115 bool empty() const { return _data.empty(); } 116 117 /// \brief Make the heap empty. 118 /// 119 /// This functon makes the heap empty. 120 /// It does not change the cross reference map. If you want to reuse 121 /// a heap that is not surely empty, you should first clear it and 122 /// then you should set the cross reference map to \c PRE_HEAP 123 /// for each item. 124 void clear() { _data.clear(); } 126 125 127 126 private: … … 130 129 131 130 bool less(const Pair &p1, const Pair &p2) const { 132 return comp(p1.second, p2.second);133 } 134 135 int find _min(const int child, const int length) {131 return _comp(p1.second, p2.second); 132 } 133 134 int findMin(const int child, const int length) { 136 135 int min=child; 137 136 if( child+3<length ) { 138 if( less( data[child+3],data[min]) )137 if( less(_data[child+3], _data[min]) ) 139 138 min=child+3; 140 if( less( data[child+2],data[min]) )139 if( less(_data[child+2], _data[min]) ) 141 140 min=child+2; 142 if( less( data[child+1],data[min]) )141 if( less(_data[child+1], _data[min]) ) 143 142 min=child+1; 144 143 } 145 144 else if( child+2<length ) { 146 if( less( data[child+2],data[min]) )145 if( less(_data[child+2], _data[min]) ) 147 146 min=child+2; 148 if( less( data[child+1],data[min]) )147 if( less(_data[child+1], _data[min]) ) 149 148 min=child+1; 150 149 } 151 150 else if( child+1<length ) { 152 if( less( data[child+1],data[min]) )151 if( less(_data[child+1], _data[min]) ) 153 152 min=child+1; 154 153 } … … 156 155 } 157 156 158 void bubble _up(int hole, Pair p) {157 void bubbleUp(int hole, Pair p) { 159 158 int par = parent(hole); 160 while( hole>0 && less(p, data[par]) ) {161 move( data[par],hole);159 while( hole>0 && less(p,_data[par]) ) { 160 move(_data[par],hole); 162 161 hole = par; 163 162 par = parent(hole); … … 166 165 } 167 166 168 void bubble _down(int hole, Pair p, int length) {167 void bubbleDown(int hole, Pair p, int length) { 169 168 int child = firstChild(hole); 170 169 while( child<length && length>1 ) { 171 child = find _min(child,length);172 if( !less( data[child], p) )170 child = findMin(child,length); 171 if( !less(_data[child], p) ) 173 172 goto ok; 174 move( data[child], hole);173 move(_data[child], hole); 175 174 hole = child; 176 175 child = firstChild(hole); … … 181 180 182 181 void move(const Pair &p, int i) { 183 data[i] = p;184 iim.set(p.first, i);182 _data[i] = p; 183 _iim.set(p.first, i); 185 184 } 186 185 187 186 public: 188 189 187 /// \brief Insert a pair of item and priority into the heap. 190 188 /// 191 /// Adds \c p.first to the heap with priority \c p.second. 189 /// This function inserts \c p.first to the heap with priority 190 /// \c p.second. 192 191 /// \param p The pair to insert. 192 /// \pre \c p.first must not be stored in the heap. 193 193 void push(const Pair &p) { 194 int n = data.size(); 195 data.resize(n+1); 196 bubble_up(n, p); 197 } 198 199 /// \brief Insert an item into the heap with the given heap. 200 /// 201 /// Adds \c i to the heap with priority \c p. 194 int n = _data.size(); 195 _data.resize(n+1); 196 bubbleUp(n, p); 197 } 198 199 /// \brief Insert an item into the heap with the given priority. 200 /// 201 /// This function inserts the given item into the heap with the 202 /// given priority. 202 203 /// \param i The item to insert. 203 204 /// \param p The priority of the item. 205 /// \pre \e i must not be stored in the heap. 204 206 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 205 207 206 /// \brief Returns the item with minimum priority relative to \c Compare. 207 /// 208 /// This method returns the item with minimum priority relative to \c 209 /// Compare. 210 /// \pre The heap must be nonempty. 211 Item top() const { return data[0].first; } 212 213 /// \brief Returns the minimum priority relative to \c Compare. 214 /// 215 /// It returns the minimum priority relative to \c Compare. 216 /// \pre The heap must be nonempty. 217 Prio prio() const { return data[0].second; } 218 219 /// \brief Deletes the item with minimum priority relative to \c Compare. 220 /// 221 /// This method deletes the item with minimum priority relative to \c 222 /// Compare from the heap. 208 /// \brief Return the item having minimum priority. 209 /// 210 /// This function returns the item having minimum priority. 211 /// \pre The heap must be non-empty. 212 Item top() const { return _data[0].first; } 213 214 /// \brief The minimum priority. 215 /// 216 /// This function returns the minimum priority. 217 /// \pre The heap must be non-empty. 218 Prio prio() const { return _data[0].second; } 219 220 /// \brief Remove the item having minimum priority. 221 /// 222 /// This function removes the item having minimum priority. 223 223 /// \pre The heap must be non-empty. 224 224 void pop() { 225 int n = data.size()-1; 226 iim.set(data[0].first, POST_HEAP); 227 if (n>0) bubble_down(0, data[n], n); 228 data.pop_back(); 229 } 230 231 /// \brief Deletes \c i from the heap. 232 /// 233 /// This method deletes item \c i from the heap. 234 /// \param i The item to erase. 235 /// \pre The item should be in the heap. 225 int n = _data.size()-1; 226 _iim.set(_data[0].first, POST_HEAP); 227 if (n>0) bubbleDown(0, _data[n], n); 228 _data.pop_back(); 229 } 230 231 /// \brief Remove the given item from the heap. 232 /// 233 /// This function removes the given item from the heap if it is 234 /// already stored. 235 /// \param i The item to delete. 236 /// \pre \e i must be in the heap. 236 237 void erase(const Item &i) { 237 int h = iim[i];238 int n = data.size()-1;239 iim.set(data[h].first, POST_HEAP);238 int h = _iim[i]; 239 int n = _data.size()-1; 240 _iim.set(_data[h].first, POST_HEAP); 240 241 if( h<n ) { 241 if( less( data[parent(h)],data[n]) )242 bubble _down(h,data[n], n);242 if( less(_data[parent(h)], _data[n]) ) 243 bubbleDown(h, _data[n], n); 243 244 else 244 bubble _up(h,data[n]);245 } 246 data.pop_back();247 } 248 249 /// \brief Returns the priority of \c i.250 /// 251 /// This function returns the priority of item \c i.252 /// \p re \c i must be in the heap.253 /// \p aram i The item.245 bubbleUp(h, _data[n]); 246 } 247 _data.pop_back(); 248 } 249 250 /// \brief The priority of the given item. 251 /// 252 /// This function returns the priority of the given item. 253 /// \param i The item. 254 /// \pre \e i must be in the heap. 254 255 Prio operator[](const Item &i) const { 255 int idx = iim[i]; 256 return data[idx].second; 257 } 258 259 /// \brief \c i gets to the heap with priority \c p independently 260 /// if \c i was already there. 261 /// 262 /// This method calls \ref push(\c i, \c p) if \c i is not stored 263 /// in the heap and sets the priority of \c i to \c p otherwise. 256 int idx = _iim[i]; 257 return _data[idx].second; 258 } 259 260 /// \brief Set the priority of an item or insert it, if it is 261 /// not stored in the heap. 262 /// 263 /// This method sets the priority of the given item if it is 264 /// already stored in the heap. Otherwise it inserts the given 265 /// item into the heap with the given priority. 264 266 /// \param i The item. 265 267 /// \param p The priority. 266 268 void set(const Item &i, const Prio &p) { 267 int idx = iim[i];269 int idx = _iim[i]; 268 270 if( idx < 0 ) 269 271 push(i,p); 270 else if( comp(p,data[idx].second) )271 bubble _up(idx, Pair(i,p));272 else if( _comp(p, _data[idx].second) ) 273 bubbleUp(idx, Pair(i,p)); 272 274 else 273 bubble_down(idx, Pair(i,p), data.size()); 274 } 275 276 /// \brief Decreases the priority of \c i to \c p. 277 /// 278 /// This method decreases the priority of item \c i to \c p. 279 /// \pre \c i must be stored in the heap with priority at least \c 280 /// p relative to \c Compare. 275 bubbleDown(idx, Pair(i,p), _data.size()); 276 } 277 278 /// \brief Decrease the priority of an item to the given value. 279 /// 280 /// This function decreases the priority of an item to the given value. 281 281 /// \param i The item. 282 282 /// \param p The priority. 283 /// \pre \e i must be stored in the heap with priority at least \e p. 283 284 void decrease(const Item &i, const Prio &p) { 284 int idx = iim[i]; 285 bubble_up(idx, Pair(i,p)); 286 } 287 288 /// \brief Increases the priority of \c i to \c p. 289 /// 290 /// This method sets the priority of item \c i to \c p. 291 /// \pre \c i must be stored in the heap with priority at most \c 292 /// p relative to \c Compare. 285 int idx = _iim[i]; 286 bubbleUp(idx, Pair(i,p)); 287 } 288 289 /// \brief Increase the priority of an item to the given value. 290 /// 291 /// This function increases the priority of an item to the given value. 293 292 /// \param i The item. 294 293 /// \param p The priority. 294 /// \pre \e i must be stored in the heap with priority at most \e p. 295 295 void increase(const Item &i, const Prio &p) { 296 int idx = iim[i];297 bubble _down(idx, Pair(i,p),data.size());298 } 299 300 /// \brief Return s if \c item is in, has already been in, or has301 /// never been in the heap.302 /// 303 /// This method returns PRE_HEAP if \c item has never been in the304 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP305 /// otherwise. In the latter case it is possible that \c item will306 /// get backto the heap again.296 int idx = _iim[i]; 297 bubbleDown(idx, Pair(i,p), _data.size()); 298 } 299 300 /// \brief Return the state of an item. 301 /// 302 /// This method returns \c PRE_HEAP if the given item has never 303 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 304 /// and \c POST_HEAP otherwise. 305 /// In the latter case it is possible that the item will get back 306 /// to the heap again. 307 307 /// \param i The item. 308 308 State state(const Item &i) const { 309 int s = iim[i];309 int s = _iim[i]; 310 310 if (s>=0) s=0; 311 311 return State(s); 312 312 } 313 313 314 /// \brief Set s the state of the \citem in the heap.315 /// 316 /// Sets the state of the \c item in the heap. It can be used to317 /// manually clear the heap when it is important to achive the318 /// better time complexity.314 /// \brief Set the state of an item in the heap. 315 /// 316 /// This function sets the state of the given item in the heap. 317 /// It can be used to manually clear the heap when it is important 318 /// to achive better time complexity. 319 319 /// \param i The item. 320 320 /// \param st The state. It should not be \c IN_HEAP. … … 324 324 case PRE_HEAP: 325 325 if (state(i) == IN_HEAP) erase(i); 326 iim[i] = st;326 _iim[i] = st; 327 327 break; 328 328 case IN_HEAP: … … 331 331 } 332 332 333 /// \brief Replaces an item in the heap. 334 /// 335 /// The \c i item is replaced with \c j item. The \c i item should 336 /// be in the heap, while the \c j should be out of the heap. The 337 /// \c i item will out of the heap and \c j will be in the heap 338 /// with the same prioriority as prevoiusly the \c i item. 333 /// \brief Replace an item in the heap. 334 /// 335 /// This function replaces item \c i with item \c j. 336 /// Item \c i must be in the heap, while \c j must be out of the heap. 337 /// After calling this method, item \c i will be out of the 338 /// heap and \c j will be in the heap with the same prioriority 339 /// as item \c i had before. 339 340 void replace(const Item& i, const Item& j) { 340 int idx = iim[i];341 iim.set(i,iim[j]);342 iim.set(j, idx);343 data[idx].first = j;341 int idx = _iim[i]; 342 _iim.set(i, _iim[j]); 343 _iim.set(j, idx); 344 _data[idx].first = j; 344 345 } 345 346 -
lemon/kary_heap.h
r701 r703 1 /* -*- C++-*-2 * 3 * This file is a part of LEMON, a generic C++ optimization library 4 * 5 * Copyright (C) 2003-200 81 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 * 5 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 20 20 #define LEMON_KARY_HEAP_H 21 21 22 ///\ingroup auxdat22 ///\ingroup heaps 23 23 ///\file 24 ///\brief Kary Heap implementation. 25 26 #include <iostream> 24 ///\brief Fourary heap implementation. 25 27 26 #include <vector> 28 27 #include <utility> … … 31 30 namespace lemon { 32 31 33 ///\ingroup auxdat 34 /// 35 ///\brief A Kary Heap implementation. 36 /// 37 ///This class implements the \e Kary \e heap data structure. A \e heap 38 ///is a data structure for storing items with specified values called \e 39 ///priorities in such a way that finding the item with minimum priority is 40 ///efficient. \c Compare specifies the ordering of the priorities. In a heap 41 ///one can change the priority of an item, add or erase an item, etc. 42 /// 43 ///\param _Prio Type of the priority of the items. 44 ///\param _ItemIntMap A read and writable Item int map, used internally 45 ///to handle the cross references. 46 ///\param _Compare A class for the ordering of the priorities. The 47 ///default is \c std::less<_Prio>. 48 /// 49 ///\sa FibHeap 50 ///\sa Dijkstra 51 ///\author Dorian Batha 52 53 template <typename _Prio, typename _ItemIntMap, 54 typename _Compare = std::less<_Prio> > 55 32 /// \ingroup heaps 33 /// 34 ///\brief K-ary heap data structure. 35 /// 36 /// This class implements the \e K-ary \e heap data structure. 37 /// It fully conforms to the \ref concepts::Heap "heap concept". 38 /// 39 /// The \ref KaryHeap "K-ary heap" is a generalization of the 40 /// \ref BinHeap "binary heap" structure, its nodes have at most 41 /// \c K children, instead of two. 42 /// \ref BinHeap and \ref FouraryHeap are specialized implementations 43 /// of this structure for <tt>K=2</tt> and <tt>K=4</tt>, respectively. 44 /// 45 /// \tparam PR Type of the priorities of the items. 46 /// \tparam IM A read-writable item map with \c int values, used 47 /// internally to handle the cross references. 48 /// \tparam CMP A functor class for comparing the priorities. 49 /// The default is \c std::less<PR>. 50 /// 51 ///\sa BinHeap 52 ///\sa FouraryHeap 53 #ifdef DOXYGEN 54 template <typename PR, typename IM, typename CMP> 55 #else 56 template <typename PR, typename IM, typename CMP = std::less<PR> > 57 #endif 56 58 class KaryHeap { 57 58 59 public: 59 /// \e60 typedef _ItemIntMapItemIntMap;61 /// \e62 typedef _PrioPrio;63 /// \e60 /// Type of the item-int map. 61 typedef IM ItemIntMap; 62 /// Type of the priorities. 63 typedef PR Prio; 64 /// Type of the items stored in the heap. 64 65 typedef typename ItemIntMap::Key Item; 65 /// \e66 /// Type of the item-priority pairs. 66 67 typedef std::pair<Item,Prio> Pair; 67 ///\e 68 typedef _Compare Compare; 69 ///\e 70 71 /// \brief Type to represent the items states. 72 /// 73 /// Each Item element have a state associated to it. It may be "in heap", 74 /// "pre heap" or "post heap". The latter two are indifferent from the 68 /// Functor type for comparing the priorities. 69 typedef CMP Compare; 70 71 /// \brief Type to represent the states of the items. 72 /// 73 /// Each item has a state associated to it. It can be "in heap", 74 /// "pre-heap" or "post-heap". The latter two are indifferent from the 75 75 /// heap's point of view, but may be useful to the user. 76 76 /// 77 /// The ItemIntMap \e should be initialized in such way that it maps78 /// PRE_HEAP (-1) to any element to be put in the heap...77 /// The item-int map must be initialized in such way that it assigns 78 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 79 79 enum State { 80 IN_HEAP = 0, 81 PRE_HEAP = -1, 82 POST_HEAP = -2 80 IN_HEAP = 0, ///< = 0. 81 PRE_HEAP = -1, ///< = -1. 82 POST_HEAP = -2 ///< = -2. 83 83 }; 84 84 85 85 private: 86 std::vector<Pair> data;87 Compare comp;88 ItemIntMap & iim;89 int K;86 std::vector<Pair> _data; 87 Compare _comp; 88 ItemIntMap &_iim; 89 int _K; 90 90 91 91 public: 92 /// \brief The constructor. 93 /// 94 /// The constructor. 95 /// \param _iim should be given to the constructor, since it is used 96 /// internally to handle the cross references. The value of the map 97 /// should be PRE_HEAP (-1) for each element. 98 explicit KaryHeap(ItemIntMap &_iim, const int &_K=32) : iim(_iim), K(_K) {} 99 100 /// \brief The constructor. 101 /// 102 /// The constructor. 103 /// \param _iim should be given to the constructor, since it is used 104 /// internally to handle the cross references. The value of the map 105 /// should be PRE_HEAP (-1) for each element. 106 /// 107 /// \param _comp The comparator function object. 108 KaryHeap(ItemIntMap &_iim, const Compare &_comp, const int &_K=32) 109 : iim(_iim), comp(_comp), K(_K) {} 110 111 112 /// The number of items stored in the heap. 113 /// 114 /// \brief Returns the number of items stored in the heap. 115 int size() const { return data.size(); } 116 117 /// \brief Checks if the heap stores no items. 118 /// 119 /// Returns \c true if and only if the heap stores no items. 120 bool empty() const { return data.empty(); } 121 122 /// \brief Make empty this heap. 123 /// 124 /// Make empty this heap. It does not change the cross reference map. 125 /// If you want to reuse what is not surely empty you should first clear 126 /// the heap and after that you should set the cross reference map for 127 /// each item to \c PRE_HEAP. 128 void clear() { data.clear(); } 92 /// \brief Constructor. 93 /// 94 /// Constructor. 95 /// \param map A map that assigns \c int values to the items. 96 /// It is used internally to handle the cross references. 97 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 98 explicit KaryHeap(ItemIntMap &map, int K=32) : _iim(map), _K(K) {} 99 100 /// \brief Constructor. 101 /// 102 /// Constructor. 103 /// \param map A map that assigns \c int values to the items. 104 /// It is used internally to handle the cross references. 105 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 106 /// \param comp The function object used for comparing the priorities. 107 KaryHeap(ItemIntMap &map, const Compare &comp, int K=32) 108 : _iim(map), _comp(comp), _K(K) {} 109 110 /// \brief The number of items stored in the heap. 111 /// 112 /// This function returns the number of items stored in the heap. 113 int size() const { return _data.size(); } 114 115 /// \brief Check if the heap is empty. 116 /// 117 /// This function returns \c true if the heap is empty. 118 bool empty() const { return _data.empty(); } 119 120 /// \brief Make the heap empty. 121 /// 122 /// This functon makes the heap empty. 123 /// It does not change the cross reference map. If you want to reuse 124 /// a heap that is not surely empty, you should first clear it and 125 /// then you should set the cross reference map to \c PRE_HEAP 126 /// for each item. 127 void clear() { _data.clear(); } 129 128 130 129 private: 131 int parent(int i) { return (i-1)/ K; }132 int first _child(int i) { returnK*i+1; }130 int parent(int i) { return (i-1)/_K; } 131 int firstChild(int i) { return _K*i+1; } 133 132 134 133 bool less(const Pair &p1, const Pair &p2) const { 135 return comp(p1.second, p2.second);136 } 137 138 int find _min(const int child, const int length) {134 return _comp(p1.second, p2.second); 135 } 136 137 int findMin(const int child, const int length) { 139 138 int min=child, i=1; 140 while( i< K && child+i<length ) {141 if( less( data[child+i],data[min]) )139 while( i<_K && child+i<length ) { 140 if( less(_data[child+i], _data[min]) ) 142 141 min=child+i; 143 142 ++i; … … 146 145 } 147 146 148 void bubble _up(int hole, Pair p) {147 void bubbleUp(int hole, Pair p) { 149 148 int par = parent(hole); 150 while( hole>0 && less(p, data[par]) ) {151 move( data[par],hole);149 while( hole>0 && less(p,_data[par]) ) { 150 move(_data[par],hole); 152 151 hole = par; 153 152 par = parent(hole); … … 156 155 } 157 156 158 void bubble _down(int hole, Pair p, int length) {157 void bubbleDown(int hole, Pair p, int length) { 159 158 if( length>1 ) { 160 int child = first _child(hole);159 int child = firstChild(hole); 161 160 while( child<length ) { 162 child = find _min(child, length);163 if( !less( data[child], p) )161 child = findMin(child, length); 162 if( !less(_data[child], p) ) 164 163 goto ok; 165 move( data[child], hole);164 move(_data[child], hole); 166 165 hole = child; 167 child = first _child(hole);166 child = firstChild(hole); 168 167 } 169 168 } … … 173 172 174 173 void move(const Pair &p, int i) { 175 data[i] = p;176 iim.set(p.first, i);174 _data[i] = p; 175 _iim.set(p.first, i); 177 176 } 178 177 … … 180 179 /// \brief Insert a pair of item and priority into the heap. 181 180 /// 182 /// Adds \c p.first to the heap with priority \c p.second. 181 /// This function inserts \c p.first to the heap with priority 182 /// \c p.second. 183 183 /// \param p The pair to insert. 184 /// \pre \c p.first must not be stored in the heap. 184 185 void push(const Pair &p) { 185 int n = data.size(); 186 data.resize(n+1); 187 bubble_up(n, p); 188 } 189 190 /// \brief Insert an item into the heap with the given heap. 191 /// 192 /// Adds \c i to the heap with priority \c p. 186 int n = _data.size(); 187 _data.resize(n+1); 188 bubbleUp(n, p); 189 } 190 191 /// \brief Insert an item into the heap with the given priority. 192 /// 193 /// This function inserts the given item into the heap with the 194 /// given priority. 193 195 /// \param i The item to insert. 194 196 /// \param p The priority of the item. 197 /// \pre \e i must not be stored in the heap. 195 198 void push(const Item &i, const Prio &p) { push(Pair(i,p)); } 196 199 197 /// \brief Returns the item with minimum priority relative to \c Compare. 198 /// 199 /// This method returns the item with minimum priority relative to \c 200 /// Compare. 201 /// \pre The heap must be nonempty. 202 Item top() const { return data[0].first; } 203 204 /// \brief Returns the minimum priority relative to \c Compare. 205 /// 206 /// It returns the minimum priority relative to \c Compare. 207 /// \pre The heap must be nonempty. 208 Prio prio() const { return data[0].second; } 209 210 /// \brief Deletes the item with minimum priority relative to \c Compare. 211 /// 212 /// This method deletes the item with minimum priority relative to \c 213 /// Compare from the heap. 200 /// \brief Return the item having minimum priority. 201 /// 202 /// This function returns the item having minimum priority. 203 /// \pre The heap must be non-empty. 204 Item top() const { return _data[0].first; } 205 206 /// \brief The minimum priority. 207 /// 208 /// This function returns the minimum priority. 209 /// \pre The heap must be non-empty. 210 Prio prio() const { return _data[0].second; } 211 212 /// \brief Remove the item having minimum priority. 213 /// 214 /// This function removes the item having minimum priority. 214 215 /// \pre The heap must be non-empty. 215 216 void pop() { 216 int n = data.size()-1; 217 iim.set(data[0].first, POST_HEAP); 218 if (n>0) bubble_down(0, data[n], n); 219 data.pop_back(); 220 } 221 222 /// \brief Deletes \c i from the heap. 223 /// 224 /// This method deletes item \c i from the heap. 225 /// \param i The item to erase. 226 /// \pre The item should be in the heap. 217 int n = _data.size()-1; 218 _iim.set(_data[0].first, POST_HEAP); 219 if (n>0) bubbleDown(0, _data[n], n); 220 _data.pop_back(); 221 } 222 223 /// \brief Remove the given item from the heap. 224 /// 225 /// This function removes the given item from the heap if it is 226 /// already stored. 227 /// \param i The item to delete. 228 /// \pre \e i must be in the heap. 227 229 void erase(const Item &i) { 228 int h = iim[i];229 int n = data.size()-1;230 iim.set(data[h].first, POST_HEAP);230 int h = _iim[i]; 231 int n = _data.size()-1; 232 _iim.set(_data[h].first, POST_HEAP); 231 233 if( h<n ) { 232 if( less( data[parent(h)],data[n]) )233 bubble _down(h,data[n], n);234 if( less(_data[parent(h)], _data[n]) ) 235 bubbleDown(h, _data[n], n); 234 236 else 235 bubble_up(h, data[n]); 236 } 237 data.pop_back(); 238 } 239 240 241 /// \brief Returns the priority of \c i. 242 /// 243 /// This function returns the priority of item \c i. 244 /// \pre \c i must be in the heap. 245 /// \param i The item. 237 bubbleUp(h, _data[n]); 238 } 239 _data.pop_back(); 240 } 241 242 /// \brief The priority of the given item. 243 /// 244 /// This function returns the priority of the given item. 245 /// \param i The item. 246 /// \pre \e i must be in the heap. 246 247 Prio operator[](const Item &i) const { 247 int idx = iim[i]; 248 return data[idx].second; 249 } 250 251 /// \brief \c i gets to the heap with priority \c p independently 252 /// if \c i was already there. 253 /// 254 /// This method calls \ref push(\c i, \c p) if \c i is not stored 255 /// in the heap and sets the priority of \c i to \c p otherwise. 248 int idx = _iim[i]; 249 return _data[idx].second; 250 } 251 252 /// \brief Set the priority of an item or insert it, if it is 253 /// not stored in the heap. 254 /// 255 /// This method sets the priority of the given item if it is 256 /// already stored in the heap. Otherwise it inserts the given 257 /// item into the heap with the given priority. 256 258 /// \param i The item. 257 259 /// \param p The priority. 258 260 void set(const Item &i, const Prio &p) { 259 int idx = iim[i];261 int idx = _iim[i]; 260 262 if( idx<0 ) 261 263 push(i,p); 262 else if( comp(p,data[idx].second) )263 bubble _up(idx, Pair(i,p));264 else if( _comp(p, _data[idx].second) ) 265 bubbleUp(idx, Pair(i,p)); 264 266 else 265 bubble_down(idx, Pair(i,p), data.size()); 266 } 267 268 /// \brief Decreases the priority of \c i to \c p. 269 /// 270 /// This method decreases the priority of item \c i to \c p. 271 /// \pre \c i must be stored in the heap with priority at least \c 272 /// p relative to \c Compare. 267 bubbleDown(idx, Pair(i,p), _data.size()); 268 } 269 270 /// \brief Decrease the priority of an item to the given value. 271 /// 272 /// This function decreases the priority of an item to the given value. 273 273 /// \param i The item. 274 274 /// \param p The priority. 275 /// \pre \e i must be stored in the heap with priority at least \e p. 275 276 void decrease(const Item &i, const Prio &p) { 276 int idx = iim[i]; 277 bubble_up(idx, Pair(i,p)); 278 } 279 280 /// \brief Increases the priority of \c i to \c p. 281 /// 282 /// This method sets the priority of item \c i to \c p. 283 /// \pre \c i must be stored in the heap with priority at most \c 284 /// p relative to \c Compare. 277 int idx = _iim[i]; 278 bubbleUp(idx, Pair(i,p)); 279 } 280 281 /// \brief Increase the priority of an item to the given value. 282 /// 283 /// This function increases the priority of an item to the given value. 285 284 /// \param i The item. 286 285 /// \param p The priority. 286 /// \pre \e i must be stored in the heap with priority at most \e p. 287 287 void increase(const Item &i, const Prio &p) { 288 int idx = iim[i];289 bubble _down(idx, Pair(i,p),data.size());290 } 291 292 /// \brief Return s if \c item is in, has already been in, or has293 /// never been in the heap.294 /// 295 /// This method returns PRE_HEAP if \c item has never been in the296 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP297 /// otherwise. In the latter case it is possible that \c item will298 /// get backto the heap again.288 int idx = _iim[i]; 289 bubbleDown(idx, Pair(i,p), _data.size()); 290 } 291 292 /// \brief Return the state of an item. 293 /// 294 /// This method returns \c PRE_HEAP if the given item has never 295 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 296 /// and \c POST_HEAP otherwise. 297 /// In the latter case it is possible that the item will get back 298 /// to the heap again. 299 299 /// \param i The item. 300 300 State state(const Item &i) const { 301 int s = iim[i];301 int s = _iim[i]; 302 302 if (s>=0) s=0; 303 303 return State(s); 304 304 } 305 305 306 /// \brief Set s the state of the \citem in the heap.307 /// 308 /// Sets the state of the \c item in the heap. It can be used to309 /// manually clear the heap when it is important to achive the310 /// better time complexity.306 /// \brief Set the state of an item in the heap. 307 /// 308 /// This function sets the state of the given item in the heap. 309 /// It can be used to manually clear the heap when it is important 310 /// to achive better time complexity. 311 311 /// \param i The item. 312 312 /// \param st The state. It should not be \c IN_HEAP. 313 313 void state(const Item& i, State st) { 314 314 switch (st) { 315 case POST_HEAP: 316 case PRE_HEAP: 317 if (state(i) == IN_HEAP) erase(i); 318 iim[i] = st; 319 break; 320 case IN_HEAP: 321 break; 322 } 323 } 324 325 /// \brief Replaces an item in the heap. 326 /// 327 /// The \c i item is replaced with \c j item. The \c i item should 328 /// be in the heap, while the \c j should be out of the heap. The 329 /// \c i item will out of the heap and \c j will be in the heap 330 /// with the same prioriority as prevoiusly the \c i item. 315 case POST_HEAP: 316 case PRE_HEAP: 317 if (state(i) == IN_HEAP) erase(i); 318 _iim[i] = st; 319 break; 320 case IN_HEAP: 321 break; 322 } 323 } 324 325 /// \brief Replace an item in the heap. 326 /// 327 /// This function replaces item \c i with item \c j. 328 /// Item \c i must be in the heap, while \c j must be out of the heap. 329 /// After calling this method, item \c i will be out of the 330 /// heap and \c j will be in the heap with the same prioriority 331 /// as item \c i had before. 331 332 void replace(const Item& i, const Item& j) { 332 int idx= iim[i];333 iim.set(i,iim[j]);334 iim.set(j, idx);335 data[idx].first=j;333 int idx=_iim[i]; 334 _iim.set(i, _iim[j]); 335 _iim.set(j, idx); 336 _data[idx].first=j; 336 337 } 337 338 -
lemon/pairing_heap.h
r702 r703 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-200 85 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 21 21 22 22 ///\file 23 ///\ingroup auxdat24 ///\brief Pairing Heap implementation.23 ///\ingroup heaps 24 ///\brief Pairing heap implementation. 25 25 26 26 #include <vector> 27 #include <utility> 27 28 #include <functional> 28 29 #include <lemon/math.h> … … 30 31 namespace lemon { 31 32 32 /// \ingroup auxdat33 /// \ingroup heaps 33 34 /// 34 35 ///\brief Pairing Heap. 35 36 /// 36 ///This class implements the \e Pairing \e heap data structure. A \e heap 37 ///is a data structure for storing items with specified values called \e 38 ///priorities in such a way that finding the item with minimum priority is 39 ///efficient. \c Compare specifies the ordering of the priorities. In a heap 40 ///one can change the priority of an item, add or erase an item, etc. 37 /// This class implements the \e pairing \e heap data structure. 38 /// It fully conforms to the \ref concepts::Heap "heap concept". 41 39 /// 42 ///The methods \ref increase and \ref erase are not efficient in a Pairing 43 ///heap. In case of many calls to these operations, it is better to use a 44 ///\ref BinHeap "binary heap". 40 /// The methods \ref increase() and \ref erase() are not efficient 41 /// in a pairing heap. In case of many calls of these operations, 42 /// it is better to use other heap structure, e.g. \ref BinHeap 43 /// "binary heap". 45 44 /// 46 ///\param _Prio Type of the priority of the items. 47 ///\param _ItemIntMap A read and writable Item int map, used internally 48 ///to handle the cross references. 49 ///\param _Compare A class for the ordering of the priorities. The 50 ///default is \c std::less<_Prio>. 51 /// 52 ///\sa BinHeap 53 ///\sa Dijkstra 54 ///\author Dorian Batha 55 45 /// \tparam PR Type of the priorities of the items. 46 /// \tparam IM A read-writable item map with \c int values, used 47 /// internally to handle the cross references. 48 /// \tparam CMP A functor class for comparing the priorities. 49 /// The default is \c std::less<PR>. 56 50 #ifdef DOXYGEN 57 template <typename _Prio, 58 typename _ItemIntMap, 59 typename _Compare> 51 template <typename PR, typename IM, typename CMP> 60 52 #else 61 template <typename _Prio, 62 typename _ItemIntMap, 63 typename _Compare = std::less<_Prio> > 53 template <typename PR, typename IM, typename CMP = std::less<PR> > 64 54 #endif 65 55 class PairingHeap { 66 56 public: 67 typedef _ItemIntMap ItemIntMap; 68 typedef _Prio Prio; 57 /// Type of the item-int map. 58 typedef IM ItemIntMap; 59 /// Type of the priorities. 60 typedef PR Prio; 61 /// Type of the items stored in the heap. 69 62 typedef typename ItemIntMap::Key Item; 70 typedef std::pair<Item,Prio> Pair; 71 typedef _Compare Compare; 63 /// Functor type for comparing the priorities. 64 typedef CMP Compare; 65 66 /// \brief Type to represent the states of the items. 67 /// 68 /// Each item has a state associated to it. It can be "in heap", 69 /// "pre-heap" or "post-heap". The latter two are indifferent from the 70 /// heap's point of view, but may be useful to the user. 71 /// 72 /// The item-int map must be initialized in such way that it assigns 73 /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap. 74 enum State { 75 IN_HEAP = 0, ///< = 0. 76 PRE_HEAP = -1, ///< = -1. 77 POST_HEAP = -2 ///< = -2. 78 }; 72 79 73 80 private: 74 81 class store; 75 82 76 std::vector<store> container;77 int minimum;78 ItemIntMap & iimap;79 Compare comp;80 int num_items;83 std::vector<store> _data; 84 int _min; 85 ItemIntMap &_iim; 86 Compare _comp; 87 int _num_items; 81 88 82 89 public: 83 ///Status of the nodes 84 enum State { 85 ///The node is in the heap 86 IN_HEAP = 0, 87 ///The node has never been in the heap 88 PRE_HEAP = -1, 89 ///The node was in the heap but it got out of it 90 POST_HEAP = -2 91 }; 92 93 /// \brief The constructor 94 /// 95 /// \c _iimap should be given to the constructor, since it is 96 /// used internally to handle the cross references. 97 explicit PairingHeap(ItemIntMap &_iimap) 98 : minimum(0), iimap(_iimap), num_items(0) {} 99 100 /// \brief The constructor 101 /// 102 /// \c _iimap should be given to the constructor, since it is used 103 /// internally to handle the cross references. \c _comp is an 104 /// object for ordering of the priorities. 105 PairingHeap(ItemIntMap &_iimap, const Compare &_comp) 106 : minimum(0), iimap(_iimap), comp(_comp), num_items(0) {} 90 /// \brief Constructor. 91 /// 92 /// Constructor. 93 /// \param map A map that assigns \c int values to the items. 94 /// It is used internally to handle the cross references. 95 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 96 explicit PairingHeap(ItemIntMap &map) 97 : _min(0), _iim(map), _num_items(0) {} 98 99 /// \brief Constructor. 100 /// 101 /// Constructor. 102 /// \param map A map that assigns \c int values to the items. 103 /// It is used internally to handle the cross references. 104 /// The assigned value must be \c PRE_HEAP (<tt>-1</tt>) for each item. 105 /// \param comp The function object used for comparing the priorities. 106 PairingHeap(ItemIntMap &map, const Compare &comp) 107 : _min(0), _iim(map), _comp(comp), _num_items(0) {} 107 108 108 109 /// \brief The number of items stored in the heap. 109 110 /// 110 /// Returns the number of items stored in the heap. 111 int size() const { return num_items; } 112 113 /// \brief Checks if the heap stores no items. 114 /// 115 /// Returns \c true if and only if the heap stores no items. 116 bool empty() const { return num_items==0; } 117 118 /// \brief Make empty this heap. 119 /// 120 /// Make empty this heap. It does not change the cross reference 121 /// map. If you want to reuse a heap what is not surely empty you 122 /// should first clear the heap and after that you should set the 123 /// cross reference map for each item to \c PRE_HEAP. 111 /// This function returns the number of items stored in the heap. 112 int size() const { return _num_items; } 113 114 /// \brief Check if the heap is empty. 115 /// 116 /// This function returns \c true if the heap is empty. 117 bool empty() const { return _num_items==0; } 118 119 /// \brief Make the heap empty. 120 /// 121 /// This functon makes the heap empty. 122 /// It does not change the cross reference map. If you want to reuse 123 /// a heap that is not surely empty, you should first clear it and 124 /// then you should set the cross reference map to \c PRE_HEAP 125 /// for each item. 124 126 void clear() { 125 container.clear(); 126 minimum = 0; 127 num_items = 0; 128 } 129 130 /// \brief \c item gets to the heap with priority \c value independently 131 /// if \c item was already there. 132 /// 133 /// This method calls \ref push(\c item, \c value) if \c item is not 134 /// stored in the heap and it calls \ref decrease(\c item, \c value) or 135 /// \ref increase(\c item, \c value) otherwise. 127 _data.clear(); 128 _min = 0; 129 _num_items = 0; 130 } 131 132 /// \brief Set the priority of an item or insert it, if it is 133 /// not stored in the heap. 134 /// 135 /// This method sets the priority of the given item if it is 136 /// already stored in the heap. Otherwise it inserts the given 137 /// item into the heap with the given priority. 138 /// \param item The item. 139 /// \param value The priority. 136 140 void set (const Item& item, const Prio& value) { 137 int i= iimap[item];138 if ( i>=0 && container[i].in ) {139 if ( comp(value, container[i].prio) ) decrease(item, value);140 if ( comp(container[i].prio, value) ) increase(item, value);141 int i=_iim[item]; 142 if ( i>=0 && _data[i].in ) { 143 if ( _comp(value, _data[i].prio) ) decrease(item, value); 144 if ( _comp(_data[i].prio, value) ) increase(item, value); 141 145 } else push(item, value); 142 146 } 143 147 144 /// \brief Adds \c item to the heap with priority \c value. 145 /// 146 /// Adds \c item to the heap with priority \c value. 147 /// \pre \c item must not be stored in the heap. 148 /// \brief Insert an item into the heap with the given priority. 149 /// 150 /// This function inserts the given item into the heap with the 151 /// given priority. 152 /// \param item The item to insert. 153 /// \param value The priority of the item. 154 /// \pre \e item must not be stored in the heap. 148 155 void push (const Item& item, const Prio& value) { 149 int i= iimap[item];156 int i=_iim[item]; 150 157 if( i<0 ) { 151 int s= container.size();152 iimap.set(item, s);158 int s=_data.size(); 159 _iim.set(item, s); 153 160 store st; 154 161 st.name=item; 155 container.push_back(st);162 _data.push_back(st); 156 163 i=s; 157 164 } else { 158 container[i].parent=container[i].child=-1;159 container[i].left_child=false;160 container[i].degree=0;161 container[i].in=true;162 } 163 164 container[i].prio=value;165 166 if ( num_items!=0 ) {167 if ( comp( value, container[minimum].prio) ) {168 fuse(i, minimum);169 minimum=i;170 } 171 else fuse( minimum,i);172 } 173 else minimum=i;174 175 ++ num_items;176 } 177 178 /// \brief Return s the item with minimum priority relative to \c Compare.179 /// 180 /// This method returns the item with minimum priority relative to \c181 /// Compare.182 /// \pre The heap must be nonempty.183 Item top() const { return container[minimum].name; } 184 185 /// \brief Returns the minimum priority relative to \c Compare.186 /// 187 /// It returns the minimum priority relative to \c Compare.188 /// \pre The heap must be nonempty.189 const Prio& prio() const { return container[minimum].prio; } 190 191 /// \brief Returns the priority of \c item.192 /// 193 /// It returns the priority of \citem.194 /// \pre \ citem must be in the heap.165 _data[i].parent=_data[i].child=-1; 166 _data[i].left_child=false; 167 _data[i].degree=0; 168 _data[i].in=true; 169 } 170 171 _data[i].prio=value; 172 173 if ( _num_items!=0 ) { 174 if ( _comp( value, _data[_min].prio) ) { 175 fuse(i,_min); 176 _min=i; 177 } 178 else fuse(_min,i); 179 } 180 else _min=i; 181 182 ++_num_items; 183 } 184 185 /// \brief Return the item having minimum priority. 186 /// 187 /// This function returns the item having minimum priority. 188 /// \pre The heap must be non-empty. 189 Item top() const { return _data[_min].name; } 190 191 /// \brief The minimum priority. 192 /// 193 /// This function returns the minimum priority. 194 /// \pre The heap must be non-empty. 195 const Prio& prio() const { return _data[_min].prio; } 196 197 /// \brief The priority of the given item. 198 /// 199 /// This function returns the priority of the given item. 200 /// \param item The item. 201 /// \pre \e item must be in the heap. 195 202 const Prio& operator[](const Item& item) const { 196 return container[iimap[item]].prio; 197 } 198 199 /// \brief Deletes the item with minimum priority relative to \c Compare. 200 /// 201 /// This method deletes the item with minimum priority relative to \c 202 /// Compare from the heap. 203 return _data[_iim[item]].prio; 204 } 205 206 /// \brief Remove the item having minimum priority. 207 /// 208 /// This function removes the item having minimum priority. 203 209 /// \pre The heap must be non-empty. 204 210 void pop() { 205 int TreeArray[ num_items];211 int TreeArray[_num_items]; 206 212 int i=0, num_child=0, child_right = 0; 207 container[minimum].in=false;208 209 if( -1!= container[minimum].child ) {210 i= container[minimum].child;213 _data[_min].in=false; 214 215 if( -1!=_data[_min].child ) { 216 i=_data[_min].child; 211 217 TreeArray[num_child] = i; 212 container[i].parent = -1;213 container[minimum].child = -1;218 _data[i].parent = -1; 219 _data[_min].child = -1; 214 220 215 221 ++num_child; 216 222 int ch=-1; 217 while( container[i].child!=-1 ) {218 ch= container[i].child;219 if( container[ch].left_child && i==container[ch].parent ) {223 while( _data[i].child!=-1 ) { 224 ch=_data[i].child; 225 if( _data[ch].left_child && i==_data[ch].parent ) { 220 226 i=ch; 221 227 //break; 222 228 } else { 223 if( container[ch].left_child ) {224 child_right= container[ch].parent;225 container[ch].parent = i;226 -- container[i].degree;229 if( _data[ch].left_child ) { 230 child_right=_data[ch].parent; 231 _data[ch].parent = i; 232 --_data[i].degree; 227 233 } 228 234 else { 229 235 child_right=ch; 230 container[i].child=-1;231 container[i].degree=0;236 _data[i].child=-1; 237 _data[i].degree=0; 232 238 } 233 container[child_right].parent = -1;239 _data[child_right].parent = -1; 234 240 TreeArray[num_child] = child_right; 235 241 i = child_right; … … 240 246 int other; 241 247 for( i=0; i<num_child-1; i+=2 ) { 242 if ( ! comp(container[TreeArray[i]].prio,243 container[TreeArray[i+1]].prio) ) {248 if ( !_comp(_data[TreeArray[i]].prio, 249 _data[TreeArray[i+1]].prio) ) { 244 250 other=TreeArray[i]; 245 251 TreeArray[i]=TreeArray[i+1]; … … 251 257 i = (0==(num_child % 2)) ? num_child-2 : num_child-1; 252 258 while(i>=2) { 253 if ( comp(container[TreeArray[i]].prio,254 container[TreeArray[i-2]].prio) ) {259 if ( _comp(_data[TreeArray[i]].prio, 260 _data[TreeArray[i-2]].prio) ) { 255 261 other=TreeArray[i]; 256 262 TreeArray[i]=TreeArray[i-2]; … … 260 266 i-=2; 261 267 } 262 minimum= TreeArray[0];268 _min = TreeArray[0]; 263 269 } 264 270 265 271 if ( 0==num_child ) { 266 minimum = container[minimum].child; 267 } 268 269 if (minimum >= 0) container[minimum].left_child = false; 270 271 --num_items; 272 } 273 274 /// \brief Deletes \c item from the heap. 275 /// 276 /// This method deletes \c item from the heap, if \c item was already 277 /// stored in the heap. It is quite inefficient in Pairing heaps. 272 _min = _data[_min].child; 273 } 274 275 if (_min >= 0) _data[_min].left_child = false; 276 277 --_num_items; 278 } 279 280 /// \brief Remove the given item from the heap. 281 /// 282 /// This function removes the given item from the heap if it is 283 /// already stored. 284 /// \param item The item to delete. 285 /// \pre \e item must be in the heap. 278 286 void erase (const Item& item) { 279 int i= iimap[item];280 if ( i>=0 && container[i].in ) {281 decrease( item, container[minimum].prio-1 );287 int i=_iim[item]; 288 if ( i>=0 && _data[i].in ) { 289 decrease( item, _data[_min].prio-1 ); 282 290 pop(); 283 291 } 284 292 } 285 293 286 /// \brief Decreases the priority of \c item to \c value. 287 /// 288 /// This method decreases the priority of \c item to \c value. 289 /// \pre \c item must be stored in the heap with priority at least \c 290 /// value relative to \c Compare. 294 /// \brief Decrease the priority of an item to the given value. 295 /// 296 /// This function decreases the priority of an item to the given value. 297 /// \param item The item. 298 /// \param value The priority. 299 /// \pre \e item must be stored in the heap with priority at least \e value. 291 300 void decrease (Item item, const Prio& value) { 292 int i= iimap[item];293 container[i].prio=value;294 int p= container[i].parent;295 296 if( container[i].left_child && i!=container[p].child ) {297 p= container[p].parent;298 } 299 300 if ( p!=-1 && comp(value,container[p].prio) ) {301 int i=_iim[item]; 302 _data[i].prio=value; 303 int p=_data[i].parent; 304 305 if( _data[i].left_child && i!=_data[p].child ) { 306 p=_data[p].parent; 307 } 308 309 if ( p!=-1 && _comp(value,_data[p].prio) ) { 301 310 cut(i,p); 302 if ( comp(container[minimum].prio,value) ) {303 fuse( minimum,i);311 if ( _comp(_data[_min].prio,value) ) { 312 fuse(_min,i); 304 313 } else { 305 fuse(i,minimum); 306 minimum=i; 307 } 308 } 309 } 310 311 /// \brief Increases the priority of \c item to \c value. 312 /// 313 /// This method sets the priority of \c item to \c value. Though 314 /// there is no precondition on the priority of \c item, this 315 /// method should be used only if it is indeed necessary to increase 316 /// (relative to \c Compare) the priority of \c item, because this 317 /// method is inefficient. 314 fuse(i,_min); 315 _min=i; 316 } 317 } 318 } 319 320 /// \brief Increase the priority of an item to the given value. 321 /// 322 /// This function increases the priority of an item to the given value. 323 /// \param item The item. 324 /// \param value The priority. 325 /// \pre \e item must be stored in the heap with priority at most \e value. 318 326 void increase (Item item, const Prio& value) { 319 327 erase(item); … … 321 329 } 322 330 323 /// \brief Returns if \c item is in, has already been in, or has never 324 /// been in the heap. 325 /// 326 /// This method returns PRE_HEAP if \c item has never been in the 327 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP 328 /// otherwise. In the latter case it is possible that \c item will 329 /// get back to the heap again. 331 /// \brief Return the state of an item. 332 /// 333 /// This method returns \c PRE_HEAP if the given item has never 334 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 335 /// and \c POST_HEAP otherwise. 336 /// In the latter case it is possible that the item will get back 337 /// to the heap again. 338 /// \param item The item. 330 339 State state(const Item &item) const { 331 int i= iimap[item];340 int i=_iim[item]; 332 341 if( i>=0 ) { 333 if( container[i].in ) i=0;342 if( _data[i].in ) i=0; 334 343 else i=-2; 335 344 } … … 337 346 } 338 347 339 /// \brief Set s the state of the \citem in the heap.340 /// 341 /// Sets the state of the \c item in the heap. It can be used to342 /// manually clear the heap when it is important to achive the343 /// better time complexity.348 /// \brief Set the state of an item in the heap. 349 /// 350 /// This function sets the state of the given item in the heap. 351 /// It can be used to manually clear the heap when it is important 352 /// to achive better time complexity. 344 353 /// \param i The item. 345 354 /// \param st The state. It should not be \c IN_HEAP. … … 349 358 case PRE_HEAP: 350 359 if (state(i) == IN_HEAP) erase(i); 351 iimap[i]=st;360 _iim[i]=st; 352 361 break; 353 362 case IN_HEAP: … … 360 369 void cut(int a, int b) { 361 370 int child_a; 362 switch ( container[a].degree) {371 switch (_data[a].degree) { 363 372 case 2: 364 child_a = container[container[a].child].parent;365 if( container[a].left_child ) {366 container[child_a].left_child=true;367 container[b].child=child_a;368 container[child_a].parent=container[a].parent;373 child_a = _data[_data[a].child].parent; 374 if( _data[a].left_child ) { 375 _data[child_a].left_child=true; 376 _data[b].child=child_a; 377 _data[child_a].parent=_data[a].parent; 369 378 } 370 379 else { 371 container[child_a].left_child=false;372 container[child_a].parent=b;373 if( a!= container[b].child )374 container[container[b].child].parent=child_a;380 _data[child_a].left_child=false; 381 _data[child_a].parent=b; 382 if( a!=_data[b].child ) 383 _data[_data[b].child].parent=child_a; 375 384 else 376 container[b].child=child_a;377 } 378 -- container[a].degree;379 container[container[a].child].parent=a;385 _data[b].child=child_a; 386 } 387 --_data[a].degree; 388 _data[_data[a].child].parent=a; 380 389 break; 381 390 382 391 case 1: 383 child_a = container[a].child;384 if( ! container[child_a].left_child ) {385 -- container[a].degree;386 if( container[a].left_child ) {387 container[child_a].left_child=true;388 container[child_a].parent=container[a].parent;389 container[b].child=child_a;392 child_a = _data[a].child; 393 if( !_data[child_a].left_child ) { 394 --_data[a].degree; 395 if( _data[a].left_child ) { 396 _data[child_a].left_child=true; 397 _data[child_a].parent=_data[a].parent; 398 _data[b].child=child_a; 390 399 } 391 400 else { 392 container[child_a].left_child=false;393 container[child_a].parent=b;394 if( a!= container[b].child )395 container[container[b].child].parent=child_a;401 _data[child_a].left_child=false; 402 _data[child_a].parent=b; 403 if( a!=_data[b].child ) 404 _data[_data[b].child].parent=child_a; 396 405 else 397 container[b].child=child_a;406 _data[b].child=child_a; 398 407 } 399 container[a].child=-1;408 _data[a].child=-1; 400 409 } 401 410 else { 402 -- container[b].degree;403 if( container[a].left_child ) {404 container[b].child =405 (1== container[b].degree) ? container[a].parent : -1;411 --_data[b].degree; 412 if( _data[a].left_child ) { 413 _data[b].child = 414 (1==_data[b].degree) ? _data[a].parent : -1; 406 415 } else { 407 if (1== container[b].degree)408 container[container[b].child].parent=b;416 if (1==_data[b].degree) 417 _data[_data[b].child].parent=b; 409 418 else 410 container[b].child=-1;419 _data[b].child=-1; 411 420 } 412 421 } … … 414 423 415 424 case 0: 416 -- container[b].degree;417 if( container[a].left_child ) {418 container[b].child =419 (0!= container[b].degree) ? container[a].parent : -1;425 --_data[b].degree; 426 if( _data[a].left_child ) { 427 _data[b].child = 428 (0!=_data[b].degree) ? _data[a].parent : -1; 420 429 } else { 421 if( 0!= container[b].degree )422 container[container[b].child].parent=b;430 if( 0!=_data[b].degree ) 431 _data[_data[b].child].parent=b; 423 432 else 424 container[b].child=-1;433 _data[b].child=-1; 425 434 } 426 435 break; 427 436 } 428 container[a].parent=-1;429 container[a].left_child=false;437 _data[a].parent=-1; 438 _data[a].left_child=false; 430 439 } 431 440 432 441 void fuse(int a, int b) { 433 int child_a = container[a].child;434 int child_b = container[b].child;435 container[a].child=b;436 container[b].parent=a;437 container[b].left_child=true;442 int child_a = _data[a].child; 443 int child_b = _data[b].child; 444 _data[a].child=b; 445 _data[b].parent=a; 446 _data[b].left_child=true; 438 447 439 448 if( -1!=child_a ) { 440 container[b].child=child_a;441 container[child_a].parent=b;442 container[child_a].left_child=false;443 ++ container[b].degree;449 _data[b].child=child_a; 450 _data[child_a].parent=b; 451 _data[child_a].left_child=false; 452 ++_data[b].degree; 444 453 445 454 if( -1!=child_b ) { 446 container[b].child=child_b;447 container[child_b].parent=child_a;448 } 449 } 450 else { ++ container[a].degree; }455 _data[b].child=child_b; 456 _data[child_b].parent=child_a; 457 } 458 } 459 else { ++_data[a].degree; } 451 460 } 452 461
Note: See TracChangeset
for help on using the changeset viewer.
