COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/pairing_heap.h @ 800:28c7ad6f8d91

Last change on this file since 800:28c7ad6f8d91 was 705:39a5b48bcace, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Small improvements in heap implementations (#301)

File size: 13.7 KB
RevLine 
[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
31namespace 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
Note: See TracBrowser for help on using the repository browser.