[703] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
[701] | 2 | * |
---|
[703] | 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
[701] | 4 | * |
---|
[703] | 5 | * Copyright (C) 2003-2009 |
---|
[701] | 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_PAIRING_HEAP_H |
---|
| 20 | #define LEMON_PAIRING_HEAP_H |
---|
| 21 | |
---|
| 22 | ///\file |
---|
[703] | 23 | ///\ingroup heaps |
---|
| 24 | ///\brief Pairing heap implementation. |
---|
[701] | 25 | |
---|
| 26 | #include <vector> |
---|
[703] | 27 | #include <utility> |
---|
[701] | 28 | #include <functional> |
---|
| 29 | #include <lemon/math.h> |
---|
| 30 | |
---|
| 31 | namespace lemon { |
---|
| 32 | |
---|
[703] | 33 | /// \ingroup heaps |
---|
[701] | 34 | /// |
---|
| 35 | ///\brief Pairing Heap. |
---|
| 36 | /// |
---|
[703] | 37 | /// This class implements the \e pairing \e heap data structure. |
---|
| 38 | /// It fully conforms to the \ref concepts::Heap "heap concept". |
---|
[701] | 39 | /// |
---|
[703] | 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". |
---|
[701] | 44 | /// |
---|
[703] | 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>. |
---|
[701] | 50 | #ifdef DOXYGEN |
---|
[703] | 51 | template <typename PR, typename IM, typename CMP> |
---|
[701] | 52 | #else |
---|
[703] | 53 | template <typename PR, typename IM, typename CMP = std::less<PR> > |
---|
[701] | 54 | #endif |
---|
| 55 | class PairingHeap { |
---|
| 56 | public: |
---|
[703] | 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. |
---|
[701] | 62 | typedef typename ItemIntMap::Key Item; |
---|
[703] | 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 | }; |
---|
[701] | 79 | |
---|
| 80 | private: |
---|
| 81 | class store; |
---|
| 82 | |
---|
[703] | 83 | std::vector<store> _data; |
---|
| 84 | int _min; |
---|
| 85 | ItemIntMap &_iim; |
---|
| 86 | Compare _comp; |
---|
| 87 | int _num_items; |
---|
[701] | 88 | |
---|
| 89 | public: |
---|
[703] | 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) {} |
---|
[701] | 98 | |
---|
[703] | 99 | /// \brief Constructor. |
---|
[701] | 100 | /// |
---|
[703] | 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) {} |
---|
[701] | 108 | |
---|
| 109 | /// \brief The number of items stored in the heap. |
---|
| 110 | /// |
---|
[703] | 111 | /// This function returns the number of items stored in the heap. |
---|
| 112 | int size() const { return _num_items; } |
---|
[701] | 113 | |
---|
[703] | 114 | /// \brief Check if the heap is empty. |
---|
[701] | 115 | /// |
---|
[703] | 116 | /// This function returns \c true if the heap is empty. |
---|
| 117 | bool empty() const { return _num_items==0; } |
---|
[701] | 118 | |
---|
[703] | 119 | /// \brief Make the heap empty. |
---|
[701] | 120 | /// |
---|
[703] | 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. |
---|
[701] | 126 | void clear() { |
---|
[703] | 127 | _data.clear(); |
---|
| 128 | _min = 0; |
---|
| 129 | _num_items = 0; |
---|
[701] | 130 | } |
---|
| 131 | |
---|
[703] | 132 | /// \brief Set the priority of an item or insert it, if it is |
---|
| 133 | /// not stored in the heap. |
---|
[701] | 134 | /// |
---|
[703] | 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. |
---|
[701] | 140 | void set (const Item& item, const Prio& value) { |
---|
[703] | 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); |
---|
[701] | 145 | } else push(item, value); |
---|
| 146 | } |
---|
| 147 | |
---|
[703] | 148 | /// \brief Insert an item into the heap with the given priority. |
---|
[701] | 149 | /// |
---|
[703] | 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. |
---|
[701] | 155 | void push (const Item& item, const Prio& value) { |
---|
[703] | 156 | int i=_iim[item]; |
---|
[701] | 157 | if( i<0 ) { |
---|
[703] | 158 | int s=_data.size(); |
---|
| 159 | _iim.set(item, s); |
---|
[701] | 160 | store st; |
---|
| 161 | st.name=item; |
---|
[703] | 162 | _data.push_back(st); |
---|
[701] | 163 | i=s; |
---|
| 164 | } else { |
---|
[703] | 165 | _data[i].parent=_data[i].child=-1; |
---|
| 166 | _data[i].left_child=false; |
---|
| 167 | _data[i].degree=0; |
---|
| 168 | _data[i].in=true; |
---|
[701] | 169 | } |
---|
| 170 | |
---|
[703] | 171 | _data[i].prio=value; |
---|
[701] | 172 | |
---|
[703] | 173 | if ( _num_items!=0 ) { |
---|
| 174 | if ( _comp( value, _data[_min].prio) ) { |
---|
| 175 | fuse(i,_min); |
---|
| 176 | _min=i; |
---|
[701] | 177 | } |
---|
[703] | 178 | else fuse(_min,i); |
---|
[701] | 179 | } |
---|
[703] | 180 | else _min=i; |
---|
[701] | 181 | |
---|
[703] | 182 | ++_num_items; |
---|
[701] | 183 | } |
---|
| 184 | |
---|
[703] | 185 | /// \brief Return the item having minimum priority. |
---|
[701] | 186 | /// |
---|
[703] | 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; } |
---|
[701] | 190 | |
---|
[703] | 191 | /// \brief The minimum priority. |
---|
[701] | 192 | /// |
---|
[703] | 193 | /// This function returns the minimum priority. |
---|
| 194 | /// \pre The heap must be non-empty. |
---|
| 195 | const Prio& prio() const { return _data[_min].prio; } |
---|
[701] | 196 | |
---|
[703] | 197 | /// \brief The priority of the given item. |
---|
[701] | 198 | /// |
---|
[703] | 199 | /// This function returns the priority of the given item. |
---|
| 200 | /// \param item The item. |
---|
| 201 | /// \pre \e item must be in the heap. |
---|
[701] | 202 | const Prio& operator[](const Item& item) const { |
---|
[703] | 203 | return _data[_iim[item]].prio; |
---|
[701] | 204 | } |
---|
| 205 | |
---|
[703] | 206 | /// \brief Remove the item having minimum priority. |
---|
[701] | 207 | /// |
---|
[703] | 208 | /// This function removes the item having minimum priority. |
---|
[701] | 209 | /// \pre The heap must be non-empty. |
---|
| 210 | void pop() { |
---|
[705] | 211 | std::vector<int> trees; |
---|
| 212 | int i=0, child_right = 0; |
---|
[703] | 213 | _data[_min].in=false; |
---|
[701] | 214 | |
---|
[703] | 215 | if( -1!=_data[_min].child ) { |
---|
| 216 | i=_data[_min].child; |
---|
[705] | 217 | trees.push_back(i); |
---|
[703] | 218 | _data[i].parent = -1; |
---|
| 219 | _data[_min].child = -1; |
---|
[701] | 220 | |
---|
| 221 | int ch=-1; |
---|
[703] | 222 | while( _data[i].child!=-1 ) { |
---|
| 223 | ch=_data[i].child; |
---|
| 224 | if( _data[ch].left_child && i==_data[ch].parent ) { |
---|
[705] | 225 | break; |
---|
[701] | 226 | } else { |
---|
[703] | 227 | if( _data[ch].left_child ) { |
---|
| 228 | child_right=_data[ch].parent; |
---|
| 229 | _data[ch].parent = i; |
---|
| 230 | --_data[i].degree; |
---|
[701] | 231 | } |
---|
| 232 | else { |
---|
| 233 | child_right=ch; |
---|
[703] | 234 | _data[i].child=-1; |
---|
| 235 | _data[i].degree=0; |
---|
[701] | 236 | } |
---|
[703] | 237 | _data[child_right].parent = -1; |
---|
[705] | 238 | trees.push_back(child_right); |
---|
[701] | 239 | i = child_right; |
---|
| 240 | } |
---|
| 241 | } |
---|
| 242 | |
---|
[705] | 243 | int num_child = trees.size(); |
---|
[701] | 244 | int other; |
---|
| 245 | for( i=0; i<num_child-1; i+=2 ) { |
---|
[705] | 246 | if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) { |
---|
| 247 | other=trees[i]; |
---|
| 248 | trees[i]=trees[i+1]; |
---|
| 249 | trees[i+1]=other; |
---|
[701] | 250 | } |
---|
[705] | 251 | fuse( trees[i], trees[i+1] ); |
---|
[701] | 252 | } |
---|
| 253 | |
---|
| 254 | i = (0==(num_child % 2)) ? num_child-2 : num_child-1; |
---|
| 255 | while(i>=2) { |
---|
[705] | 256 | if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) { |
---|
| 257 | other=trees[i]; |
---|
| 258 | trees[i]=trees[i-2]; |
---|
| 259 | trees[i-2]=other; |
---|
[701] | 260 | } |
---|
[705] | 261 | fuse( trees[i-2], trees[i] ); |
---|
[701] | 262 | i-=2; |
---|
| 263 | } |
---|
[705] | 264 | _min = trees[0]; |
---|
[701] | 265 | } |
---|
[705] | 266 | else { |
---|
[703] | 267 | _min = _data[_min].child; |
---|
[701] | 268 | } |
---|
| 269 | |
---|
[703] | 270 | if (_min >= 0) _data[_min].left_child = false; |
---|
| 271 | --_num_items; |
---|
[701] | 272 | } |
---|
| 273 | |
---|
[703] | 274 | /// \brief Remove the given item from the heap. |
---|
[701] | 275 | /// |
---|
[703] | 276 | /// This function removes the given item from the heap if it is |
---|
| 277 | /// already stored. |
---|
| 278 | /// \param item The item to delete. |
---|
| 279 | /// \pre \e item must be in the heap. |
---|
[701] | 280 | void erase (const Item& item) { |
---|
[703] | 281 | int i=_iim[item]; |
---|
| 282 | if ( i>=0 && _data[i].in ) { |
---|
| 283 | decrease( item, _data[_min].prio-1 ); |
---|
[701] | 284 | pop(); |
---|
| 285 | } |
---|
| 286 | } |
---|
| 287 | |
---|
[703] | 288 | /// \brief Decrease the priority of an item to the given value. |
---|
[701] | 289 | /// |
---|
[703] | 290 | /// This function decreases the priority of an item to the given value. |
---|
| 291 | /// \param item The item. |
---|
| 292 | /// \param value The priority. |
---|
| 293 | /// \pre \e item must be stored in the heap with priority at least \e value. |
---|
[701] | 294 | void decrease (Item item, const Prio& value) { |
---|
[703] | 295 | int i=_iim[item]; |
---|
| 296 | _data[i].prio=value; |
---|
| 297 | int p=_data[i].parent; |
---|
[701] | 298 | |
---|
[703] | 299 | if( _data[i].left_child && i!=_data[p].child ) { |
---|
| 300 | p=_data[p].parent; |
---|
[701] | 301 | } |
---|
| 302 | |
---|
[703] | 303 | if ( p!=-1 && _comp(value,_data[p].prio) ) { |
---|
[701] | 304 | cut(i,p); |
---|
[703] | 305 | if ( _comp(_data[_min].prio,value) ) { |
---|
| 306 | fuse(_min,i); |
---|
[701] | 307 | } else { |
---|
[703] | 308 | fuse(i,_min); |
---|
| 309 | _min=i; |
---|
[701] | 310 | } |
---|
| 311 | } |
---|
| 312 | } |
---|
| 313 | |
---|
[703] | 314 | /// \brief Increase the priority of an item to the given value. |
---|
[701] | 315 | /// |
---|
[703] | 316 | /// This function increases the priority of an item to the given value. |
---|
| 317 | /// \param item The item. |
---|
| 318 | /// \param value The priority. |
---|
| 319 | /// \pre \e item must be stored in the heap with priority at most \e value. |
---|
[701] | 320 | void increase (Item item, const Prio& value) { |
---|
| 321 | erase(item); |
---|
| 322 | push(item,value); |
---|
| 323 | } |
---|
| 324 | |
---|
[703] | 325 | /// \brief Return the state of an item. |
---|
[701] | 326 | /// |
---|
[703] | 327 | /// This method returns \c PRE_HEAP if the given item has never |
---|
| 328 | /// been in the heap, \c IN_HEAP if it is in the heap at the moment, |
---|
| 329 | /// and \c POST_HEAP otherwise. |
---|
| 330 | /// In the latter case it is possible that the item will get back |
---|
| 331 | /// to the heap again. |
---|
| 332 | /// \param item The item. |
---|
[701] | 333 | State state(const Item &item) const { |
---|
[703] | 334 | int i=_iim[item]; |
---|
[701] | 335 | if( i>=0 ) { |
---|
[703] | 336 | if( _data[i].in ) i=0; |
---|
[701] | 337 | else i=-2; |
---|
| 338 | } |
---|
| 339 | return State(i); |
---|
| 340 | } |
---|
| 341 | |
---|
[703] | 342 | /// \brief Set the state of an item in the heap. |
---|
[701] | 343 | /// |
---|
[703] | 344 | /// This function sets the state of the given item in the heap. |
---|
| 345 | /// It can be used to manually clear the heap when it is important |
---|
| 346 | /// to achive better time complexity. |
---|
[701] | 347 | /// \param i The item. |
---|
| 348 | /// \param st The state. It should not be \c IN_HEAP. |
---|
| 349 | void state(const Item& i, State st) { |
---|
| 350 | switch (st) { |
---|
| 351 | case POST_HEAP: |
---|
| 352 | case PRE_HEAP: |
---|
| 353 | if (state(i) == IN_HEAP) erase(i); |
---|
[703] | 354 | _iim[i]=st; |
---|
[701] | 355 | break; |
---|
| 356 | case IN_HEAP: |
---|
| 357 | break; |
---|
| 358 | } |
---|
| 359 | } |
---|
| 360 | |
---|
| 361 | private: |
---|
| 362 | |
---|
| 363 | void cut(int a, int b) { |
---|
| 364 | int child_a; |
---|
[703] | 365 | switch (_data[a].degree) { |
---|
[701] | 366 | case 2: |
---|
[703] | 367 | child_a = _data[_data[a].child].parent; |
---|
| 368 | if( _data[a].left_child ) { |
---|
| 369 | _data[child_a].left_child=true; |
---|
| 370 | _data[b].child=child_a; |
---|
| 371 | _data[child_a].parent=_data[a].parent; |
---|
[701] | 372 | } |
---|
| 373 | else { |
---|
[703] | 374 | _data[child_a].left_child=false; |
---|
| 375 | _data[child_a].parent=b; |
---|
| 376 | if( a!=_data[b].child ) |
---|
| 377 | _data[_data[b].child].parent=child_a; |
---|
[701] | 378 | else |
---|
[703] | 379 | _data[b].child=child_a; |
---|
[701] | 380 | } |
---|
[703] | 381 | --_data[a].degree; |
---|
| 382 | _data[_data[a].child].parent=a; |
---|
[701] | 383 | break; |
---|
| 384 | |
---|
| 385 | case 1: |
---|
[703] | 386 | child_a = _data[a].child; |
---|
| 387 | if( !_data[child_a].left_child ) { |
---|
| 388 | --_data[a].degree; |
---|
| 389 | if( _data[a].left_child ) { |
---|
| 390 | _data[child_a].left_child=true; |
---|
| 391 | _data[child_a].parent=_data[a].parent; |
---|
| 392 | _data[b].child=child_a; |
---|
[701] | 393 | } |
---|
| 394 | else { |
---|
[703] | 395 | _data[child_a].left_child=false; |
---|
| 396 | _data[child_a].parent=b; |
---|
| 397 | if( a!=_data[b].child ) |
---|
| 398 | _data[_data[b].child].parent=child_a; |
---|
[701] | 399 | else |
---|
[703] | 400 | _data[b].child=child_a; |
---|
[701] | 401 | } |
---|
[703] | 402 | _data[a].child=-1; |
---|
[701] | 403 | } |
---|
| 404 | else { |
---|
[703] | 405 | --_data[b].degree; |
---|
| 406 | if( _data[a].left_child ) { |
---|
| 407 | _data[b].child = |
---|
| 408 | (1==_data[b].degree) ? _data[a].parent : -1; |
---|
[701] | 409 | } else { |
---|
[703] | 410 | if (1==_data[b].degree) |
---|
| 411 | _data[_data[b].child].parent=b; |
---|
[701] | 412 | else |
---|
[703] | 413 | _data[b].child=-1; |
---|
[701] | 414 | } |
---|
| 415 | } |
---|
| 416 | break; |
---|
| 417 | |
---|
| 418 | case 0: |
---|
[703] | 419 | --_data[b].degree; |
---|
| 420 | if( _data[a].left_child ) { |
---|
| 421 | _data[b].child = |
---|
| 422 | (0!=_data[b].degree) ? _data[a].parent : -1; |
---|
[701] | 423 | } else { |
---|
[703] | 424 | if( 0!=_data[b].degree ) |
---|
| 425 | _data[_data[b].child].parent=b; |
---|
[701] | 426 | else |
---|
[703] | 427 | _data[b].child=-1; |
---|
[701] | 428 | } |
---|
| 429 | break; |
---|
| 430 | } |
---|
[703] | 431 | _data[a].parent=-1; |
---|
| 432 | _data[a].left_child=false; |
---|
[701] | 433 | } |
---|
| 434 | |
---|
| 435 | void fuse(int a, int b) { |
---|
[703] | 436 | int child_a = _data[a].child; |
---|
| 437 | int child_b = _data[b].child; |
---|
| 438 | _data[a].child=b; |
---|
| 439 | _data[b].parent=a; |
---|
| 440 | _data[b].left_child=true; |
---|
[701] | 441 | |
---|
| 442 | if( -1!=child_a ) { |
---|
[703] | 443 | _data[b].child=child_a; |
---|
| 444 | _data[child_a].parent=b; |
---|
| 445 | _data[child_a].left_child=false; |
---|
| 446 | ++_data[b].degree; |
---|
[701] | 447 | |
---|
| 448 | if( -1!=child_b ) { |
---|
[703] | 449 | _data[b].child=child_b; |
---|
| 450 | _data[child_b].parent=child_a; |
---|
[701] | 451 | } |
---|
| 452 | } |
---|
[703] | 453 | else { ++_data[a].degree; } |
---|
[701] | 454 | } |
---|
| 455 | |
---|
| 456 | class store { |
---|
| 457 | friend class PairingHeap; |
---|
| 458 | |
---|
| 459 | Item name; |
---|
| 460 | int parent; |
---|
| 461 | int child; |
---|
| 462 | bool left_child; |
---|
| 463 | int degree; |
---|
| 464 | bool in; |
---|
| 465 | Prio prio; |
---|
| 466 | |
---|
| 467 | store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {} |
---|
| 468 | }; |
---|
| 469 | }; |
---|
| 470 | |
---|
| 471 | } //namespace lemon |
---|
| 472 | |
---|
| 473 | #endif //LEMON_PAIRING_HEAP_H |
---|
| 474 | |
---|