1 /* -*- 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-2010 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). 8 * 9 * Permission to use, modify and distribute this software is granted 10 * provided that this copyright notice appears in all copies. For 11 * precise terms see the accompanying LICENSE file. 12 * 13 * This software is provided "AS IS" with no warranty of any kind, 14 * express or implied, and with no claim as to its suitability for any 15 * purpose. 16 * 17 */ 18 19 #ifndef LEMON_BINOMIAL_HEAP_H 20 #define LEMON_BINOMIAL_HEAP_H 21 22 ///\file 23 ///\ingroup heaps 24 ///\brief Binomial Heap implementation. 25 26 #include <vector> 27 #include <utility> 28 #include <functional> 29 #include <lemon/math.h> 30 #include <lemon/counter.h> 31 32 namespace lemon { 33 34 /// \ingroup heaps 35 /// 36 ///\brief Binomial heap data structure. 37 /// 38 /// This class implements the \e binomial \e heap data structure. 39 /// It fully conforms to the \ref concepts::Heap "heap concept". 40 /// 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". 45 /// 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>. 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 class BinomialHeap { 57 public: 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. 63 typedef typename ItemIntMap::Key Item; 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 }; 80 81 private: 82 class Store; 83 84 std::vector<Store> _data; 85 int _min, _head; 86 ItemIntMap &_iim; 87 Compare _comp; 88 int _num_items; 89 90 public: 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. BinomialHeap(ItemIntMap & map)97 explicit BinomialHeap(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. BinomialHeap(ItemIntMap & map,const Compare & comp)107 BinomialHeap(ItemIntMap &map, const Compare &comp) 108 : _min(0), _head(-1), _iim(map), _comp(comp), _num_items(0) {} 109 110 /// \brief The number of items stored in the heap. 111 /// 112 /// This function returns the number of items stored in the heap. size()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. 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. clear()127 void clear() { 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. set(const Item & item,const Prio & value)139 void set (const Item& item, const Prio& 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); 144 } else push(item, value); 145 } 146 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. push(const Item & item,const Prio & value)154 void push (const Item& item, const Prio& value) { 155 int i=_iim[item]; 156 if ( i<0 ) { 157 int s=_data.size(); 158 _iim.set( item,s ); 159 Store st; 160 st.name=item; 161 st.prio=value; 162 _data.push_back(st); 163 i=s; 164 } 165 else { 166 _data[i].parent=_data[i].right_neighbor=_data[i].child=-1; 167 _data[i].degree=0; 168 _data[i].in=true; 169 _data[i].prio=value; 170 } 171 172 if( 0==_num_items ) { 173 _head=i; 174 _min=i; 175 } else { 176 merge(i); 177 if( _comp(_data[i].prio, _data[_min].prio) ) _min=i; 178 } 179 ++_num_items; 180 } 181 182 /// \brief Return the item having minimum priority. 183 /// 184 /// This function returns the item having minimum priority. 185 /// \pre The heap must be non-empty. top()186 Item top() const { return _data[_min].name; } 187 188 /// \brief The minimum priority. 189 /// 190 /// This function returns the minimum priority. 191 /// \pre The heap must be non-empty. prio()192 Prio prio() const { return _data[_min].prio; } 193 194 /// \brief The priority of the given item. 195 /// 196 /// This function returns the priority of the given item. 197 /// \param item The item. 198 /// \pre \e item must be in the heap. 199 const Prio& operator[](const Item& item) const { 200 return _data[_iim[item]].prio; 201 } 202 203 /// \brief Remove the item having minimum priority. 204 /// 205 /// This function removes the item having minimum priority. 206 /// \pre The heap must be non-empty. pop()207 void pop() { 208 _data[_min].in=false; 209 210 int head_child=-1; 211 if ( _data[_min].child!=-1 ) { 212 int child=_data[_min].child; 213 int neighb; 214 while( child!=-1 ) { 215 neighb=_data[child].right_neighbor; 216 _data[child].parent=-1; 217 _data[child].right_neighbor=head_child; 218 head_child=child; 219 child=neighb; 220 } 221 } 222 223 if ( _data[_head].right_neighbor==-1 ) { 224 // there was only one root 225 _head=head_child; 226 } 227 else { 228 // there were more roots 229 if( _head!=_min ) { unlace(_min); } 230 else { _head=_data[_head].right_neighbor; } 231 merge(head_child); 232 } 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. erase(const Item & item)243 void erase (const Item& item) { 244 int i=_iim[item]; 245 if ( i >= 0 && _data[i].in ) { 246 decrease( item, _data[_min].prio-1 ); 247 pop(); 248 } 249 } 250 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. decrease(Item item,const Prio & value)257 void decrease (Item item, const Prio& value) { 258 int i=_iim[item]; 259 int p=_data[i].parent; 260 _data[i].prio=value; 261 262 while( p!=-1 && _comp(value, _data[p].prio) ) { 263 _data[i].name=_data[p].name; 264 _data[i].prio=_data[p].prio; 265 _data[p].name=item; 266 _data[p].prio=value; 267 _iim[_data[i].name]=i; 268 i=p; 269 p=_data[p].parent; 270 } 271 _iim[item]=i; 272 if ( _comp(value, _data[_min].prio) ) _min=i; 273 } 274 275 /// \brief Increase the priority of an item to the given value. 276 /// 277 /// This function increases the priority of an item to the given value. 278 /// \param item The item. 279 /// \param value The priority. 280 /// \pre \e item must be stored in the heap with priority at most \e value. increase(Item item,const Prio & value)281 void increase (Item item, const Prio& value) { 282 erase(item); 283 push(item, value); 284 } 285 286 /// \brief Return the state of an item. 287 /// 288 /// This method returns \c PRE_HEAP if the given item has never 289 /// been in the heap, \c IN_HEAP if it is in the heap at the moment, 290 /// and \c POST_HEAP otherwise. 291 /// In the latter case it is possible that the item will get back 292 /// to the heap again. 293 /// \param item The item. state(const Item & item)294 State state(const Item &item) const { 295 int i=_iim[item]; 296 if( i>=0 ) { 297 if ( _data[i].in ) i=0; 298 else i=-2; 299 } 300 return State(i); 301 } 302 303 /// \brief Set the state of an item in the heap. 304 /// 305 /// This function sets the state of the given item in the heap. 306 /// It can be used to manually clear the heap when it is important 307 /// to achive better time complexity. 308 /// \param i The item. 309 /// \param st The state. It should not be \c IN_HEAP. state(const Item & i,State st)310 void state(const Item& i, State st) { 311 switch (st) { 312 case POST_HEAP: 313 case PRE_HEAP: 314 if (state(i) == IN_HEAP) { 315 erase(i); 316 } 317 _iim[i] = st; 318 break; 319 case IN_HEAP: 320 break; 321 } 322 } 323 324 private: 325 326 // Find the minimum of the roots findMin()327 int findMin() { 328 if( _head!=-1 ) { 329 int min_loc=_head, min_val=_data[_head].prio; 330 for( int x=_data[_head].right_neighbor; x!=-1; 331 x=_data[x].right_neighbor ) { 332 if( _comp( _data[x].prio,min_val ) ) { 333 min_val=_data[x].prio; 334 min_loc=x; 335 } 336 } 337 return min_loc; 338 } 339 else return -1; 340 } 341 342 // Merge the heap with another heap starting at the given position merge(int a)343 void merge(int a) { 344 if( _head==-1 || a==-1 ) return; 345 if( _data[a].right_neighbor==-1 && 346 _data[a].degree<=_data[_head].degree ) { 347 _data[a].right_neighbor=_head; 348 _head=a; 349 } else { 350 interleave(a); 351 } 352 if( _data[_head].right_neighbor==-1 ) return; 353 354 int x=_head; 355 int x_prev=-1, x_next=_data[x].right_neighbor; 356 while( x_next!=-1 ) { 357 if( _data[x].degree!=_data[x_next].degree || 358 ( _data[x_next].right_neighbor!=-1 && 359 _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) { 360 x_prev=x; 361 x=x_next; 362 } 363 else { 364 if( _comp(_data[x_next].prio,_data[x].prio) ) { 365 if( x_prev==-1 ) { 366 _head=x_next; 367 } else { 368 _data[x_prev].right_neighbor=x_next; 369 } 370 fuse(x,x_next); 371 x=x_next; 372 } 373 else { 374 _data[x].right_neighbor=_data[x_next].right_neighbor; 375 fuse(x_next,x); 376 } 377 } 378 x_next=_data[x].right_neighbor; 379 } 380 } 381 382 // Interleave the elements of the given list into the list of the roots interleave(int a)383 void interleave(int a) { 384 int p=_head, q=a; 385 int curr=_data.size(); 386 _data.push_back(Store()); 387 388 while( p!=-1 || q!=-1 ) { 389 if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) { 390 _data[curr].right_neighbor=p; 391 curr=p; 392 p=_data[p].right_neighbor; 393 } 394 else { 395 _data[curr].right_neighbor=q; 396 curr=q; 397 q=_data[q].right_neighbor; 398 } 399 } 400 401 _head=_data.back().right_neighbor; 402 _data.pop_back(); 403 } 404 405 // Lace node a under node b fuse(int a,int b)406 void fuse(int a, int b) { 407 _data[a].parent=b; 408 _data[a].right_neighbor=_data[b].child; 409 _data[b].child=a; 410 411 ++_data[b].degree; 412 } 413 414 // Unlace node a (if it has siblings) unlace(int a)415 void unlace(int a) { 416 int neighb=_data[a].right_neighbor; 417 int other=_head; 418 419 while( _data[other].right_neighbor!=a ) 420 other=_data[other].right_neighbor; 421 _data[other].right_neighbor=neighb; 422 } 423 424 private: 425 426 class Store { 427 friend class BinomialHeap; 428 429 Item name; 430 int parent; 431 int right_neighbor; 432 int child; 433 int degree; 434 bool in; 435 Prio prio; 436 Store()437 Store() : parent(-1), right_neighbor(-1), child(-1), degree(0), 438 in(true) {} 439 }; 440 }; 441 442 } //namespace lemon 443 444 #endif //LEMON_BINOMIAL_HEAP_H 445 446