COIN-OR::LEMON - Graph Library

source: lemon/lemon/pairing_heap.h @ 833:e20173729589

Last change on this file since 833:e20173729589 was 752:39a5b48bcace, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Small improvements in heap implementations (#301)

File size: 13.7 KB
RevLine 
[750]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[748]2 *
[750]3 * This file is a part of LEMON, a generic C++ optimization library.
[748]4 *
[750]5 * Copyright (C) 2003-2009
[748]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
[750]23///\ingroup heaps
24///\brief Pairing heap implementation.
[748]25
26#include <vector>
[750]27#include <utility>
[748]28#include <functional>
29#include <lemon/math.h>
30
31namespace lemon {
32
[750]33  /// \ingroup heaps
[748]34  ///
35  ///\brief Pairing Heap.
36  ///
[750]37  /// This class implements the \e pairing \e heap data structure.
38  /// It fully conforms to the \ref concepts::Heap "heap concept".
[748]39  ///
[750]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".
[748]44  ///
[750]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>.
[748]50#ifdef DOXYGEN
[750]51  template <typename PR, typename IM, typename CMP>
[748]52#else
[750]53  template <typename PR, typename IM, typename CMP = std::less<PR> >
[748]54#endif
55  class PairingHeap {
56  public:
[750]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.
[748]62    typedef typename ItemIntMap::Key Item;
[750]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    };
[748]79
80  private:
81    class store;
82
[750]83    std::vector<store> _data;
84    int _min;
85    ItemIntMap &_iim;
86    Compare _comp;
87    int _num_items;
[748]88
89  public:
[750]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) {}
[748]98
[750]99    /// \brief Constructor.
[748]100    ///
[750]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) {}
[748]108
109    /// \brief The number of items stored in the heap.
110    ///
[750]111    /// This function returns the number of items stored in the heap.
112    int size() const { return _num_items; }
[748]113
[750]114    /// \brief Check if the heap is empty.
[748]115    ///
[750]116    /// This function returns \c true if the heap is empty.
117    bool empty() const { return _num_items==0; }
[748]118
[750]119    /// \brief Make the heap empty.
[748]120    ///
[750]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.
[748]126    void clear() {
[750]127      _data.clear();
128      _min = 0;
129      _num_items = 0;
[748]130    }
131
[750]132    /// \brief Set the priority of an item or insert it, if it is
133    /// not stored in the heap.
[748]134    ///
[750]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.
[748]140    void set (const Item& item, const Prio& value) {
[750]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);
[748]145      } else push(item, value);
146    }
147
[750]148    /// \brief Insert an item into the heap with the given priority.
[748]149    ///
[750]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.
[748]155    void push (const Item& item, const Prio& value) {
[750]156      int i=_iim[item];
[748]157      if( i<0 ) {
[750]158        int s=_data.size();
159        _iim.set(item, s);
[748]160        store st;
161        st.name=item;
[750]162        _data.push_back(st);
[748]163        i=s;
164      } else {
[750]165        _data[i].parent=_data[i].child=-1;
166        _data[i].left_child=false;
167        _data[i].degree=0;
168        _data[i].in=true;
[748]169      }
170
[750]171      _data[i].prio=value;
[748]172
[750]173      if ( _num_items!=0 ) {
174        if ( _comp( value, _data[_min].prio) ) {
175          fuse(i,_min);
176          _min=i;
[748]177        }
[750]178        else fuse(_min,i);
[748]179      }
[750]180      else _min=i;
[748]181
[750]182      ++_num_items;
[748]183    }
184
[750]185    /// \brief Return the item having minimum priority.
[748]186    ///
[750]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; }
[748]190
[750]191    /// \brief The minimum priority.
[748]192    ///
[750]193    /// This function returns the minimum priority.
194    /// \pre The heap must be non-empty.
195    const Prio& prio() const { return _data[_min].prio; }
[748]196
[750]197    /// \brief The priority of the given item.
[748]198    ///
[750]199    /// This function returns the priority of the given item.
200    /// \param item The item.
201    /// \pre \e item must be in the heap.
[748]202    const Prio& operator[](const Item& item) const {
[750]203      return _data[_iim[item]].prio;
[748]204    }
205
[750]206    /// \brief Remove the item having minimum priority.
[748]207    ///
[750]208    /// This function removes the item having minimum priority.
[748]209    /// \pre The heap must be non-empty.
210    void pop() {
[752]211      std::vector<int> trees;
212      int i=0, child_right = 0;
[750]213      _data[_min].in=false;
[748]214
[750]215      if( -1!=_data[_min].child ) {
216        i=_data[_min].child;
[752]217        trees.push_back(i);
[750]218        _data[i].parent = -1;
219        _data[_min].child = -1;
[748]220
221        int ch=-1;
[750]222        while( _data[i].child!=-1 ) {
223          ch=_data[i].child;
224          if( _data[ch].left_child && i==_data[ch].parent ) {
[752]225            break;
[748]226          } else {
[750]227            if( _data[ch].left_child ) {
228              child_right=_data[ch].parent;
229              _data[ch].parent = i;
230              --_data[i].degree;
[748]231            }
232            else {
233              child_right=ch;
[750]234              _data[i].child=-1;
235              _data[i].degree=0;
[748]236            }
[750]237            _data[child_right].parent = -1;
[752]238            trees.push_back(child_right);
[748]239            i = child_right;
240          }
241        }
242
[752]243        int num_child = trees.size();
[748]244        int other;
245        for( i=0; i<num_child-1; i+=2 ) {
[752]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;
[748]250          }
[752]251          fuse( trees[i], trees[i+1] );
[748]252        }
253
254        i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
255        while(i>=2) {
[752]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;
[748]260          }
[752]261          fuse( trees[i-2], trees[i] );
[748]262          i-=2;
263        }
[752]264        _min = trees[0];
[748]265      }
[752]266      else {
[750]267        _min = _data[_min].child;
[748]268      }
269
[750]270      if (_min >= 0) _data[_min].left_child = false;
271      --_num_items;
[748]272    }
273
[750]274    /// \brief Remove the given item from the heap.
[748]275    ///
[750]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.
[748]280    void erase (const Item& item) {
[750]281      int i=_iim[item];
282      if ( i>=0 && _data[i].in ) {
283        decrease( item, _data[_min].prio-1 );
[748]284        pop();
285      }
286    }
287
[750]288    /// \brief Decrease the priority of an item to the given value.
[748]289    ///
[750]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.
[748]294    void decrease (Item item, const Prio& value) {
[750]295      int i=_iim[item];
296      _data[i].prio=value;
297      int p=_data[i].parent;
[748]298
[750]299      if( _data[i].left_child && i!=_data[p].child ) {
300        p=_data[p].parent;
[748]301      }
302
[750]303      if ( p!=-1 && _comp(value,_data[p].prio) ) {
[748]304        cut(i,p);
[750]305        if ( _comp(_data[_min].prio,value) ) {
306          fuse(_min,i);
[748]307        } else {
[750]308          fuse(i,_min);
309          _min=i;
[748]310        }
311      }
312    }
313
[750]314    /// \brief Increase the priority of an item to the given value.
[748]315    ///
[750]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.
[748]320    void increase (Item item, const Prio& value) {
321      erase(item);
322      push(item,value);
323    }
324
[750]325    /// \brief Return the state of an item.
[748]326    ///
[750]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.
[748]333    State state(const Item &item) const {
[750]334      int i=_iim[item];
[748]335      if( i>=0 ) {
[750]336        if( _data[i].in ) i=0;
[748]337        else i=-2;
338      }
339      return State(i);
340    }
341
[750]342    /// \brief Set the state of an item in the heap.
[748]343    ///
[750]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.
[748]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);
[750]354        _iim[i]=st;
[748]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;
[750]365      switch (_data[a].degree) {
[748]366        case 2:
[750]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;
[748]372          }
373          else {
[750]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;
[748]378            else
[750]379              _data[b].child=child_a;
[748]380          }
[750]381          --_data[a].degree;
382          _data[_data[a].child].parent=a;
[748]383          break;
384
385        case 1:
[750]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;
[748]393            }
394            else {
[750]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;
[748]399              else
[750]400                _data[b].child=child_a;
[748]401            }
[750]402            _data[a].child=-1;
[748]403          }
404          else {
[750]405            --_data[b].degree;
406            if( _data[a].left_child ) {
407              _data[b].child =
408                (1==_data[b].degree) ? _data[a].parent : -1;
[748]409            } else {
[750]410              if (1==_data[b].degree)
411                _data[_data[b].child].parent=b;
[748]412              else
[750]413                _data[b].child=-1;
[748]414            }
415          }
416          break;
417
418        case 0:
[750]419          --_data[b].degree;
420          if( _data[a].left_child ) {
421            _data[b].child =
422              (0!=_data[b].degree) ? _data[a].parent : -1;
[748]423          } else {
[750]424            if( 0!=_data[b].degree )
425              _data[_data[b].child].parent=b;
[748]426            else
[750]427              _data[b].child=-1;
[748]428          }
429          break;
430      }
[750]431      _data[a].parent=-1;
432      _data[a].left_child=false;
[748]433    }
434
435    void fuse(int a, int b) {
[750]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;
[748]441
442      if( -1!=child_a ) {
[750]443        _data[b].child=child_a;
444        _data[child_a].parent=b;
445        _data[child_a].left_child=false;
446        ++_data[b].degree;
[748]447
448        if( -1!=child_b ) {
[750]449           _data[b].child=child_b;
450           _data[child_b].parent=child_a;
[748]451        }
452      }
[750]453      else { ++_data[a].degree; }
[748]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.