COIN-OR::LEMON - Graph Library

source: lemon/lemon/pairing_heap.h @ 750:bb3392fe91f2

Last change on this file since 750:bb3392fe91f2 was 750:bb3392fe91f2, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Improve and unify the doc + names in the new heaps (#301)

File size: 13.8 KB
Line 
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-2009
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
23///\ingroup heaps
24///\brief Pairing heap implementation.
25
26#include <vector>
27#include <utility>
28#include <functional>
29#include <lemon/math.h>
30
31namespace lemon {
32
33  /// \ingroup heaps
34  ///
35  ///\brief Pairing Heap.
36  ///
37  /// This class implements the \e pairing \e heap data structure.
38  /// It fully conforms to the \ref concepts::Heap "heap concept".
39  ///
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".
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#ifdef DOXYGEN
51  template <typename PR, typename IM, typename CMP>
52#else
53  template <typename PR, typename IM, typename CMP = std::less<PR> >
54#endif
55  class PairingHeap {
56  public:
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.
62    typedef typename ItemIntMap::Key Item;
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    };
79
80  private:
81    class store;
82
83    std::vector<store> _data;
84    int _min;
85    ItemIntMap &_iim;
86    Compare _comp;
87    int _num_items;
88
89  public:
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) {}
108
109    /// \brief The number of items stored in the heap.
110    ///
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.
126    void clear() {
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.
140    void set (const Item& item, const Prio& 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);
145      } else push(item, value);
146    }
147
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.
155    void push (const Item& item, const Prio& value) {
156      int i=_iim[item];
157      if( i<0 ) {
158        int s=_data.size();
159        _iim.set(item, s);
160        store st;
161        st.name=item;
162        _data.push_back(st);
163        i=s;
164      } else {
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.
202    const Prio& operator[](const Item& item) const {
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.
209    /// \pre The heap must be non-empty.
210    void pop() {
211      int TreeArray[_num_items];
212      int i=0, num_child=0, child_right = 0;
213      _data[_min].in=false;
214
215      if( -1!=_data[_min].child ) {
216        i=_data[_min].child;
217        TreeArray[num_child] = i;
218        _data[i].parent = -1;
219        _data[_min].child = -1;
220
221        ++num_child;
222        int ch=-1;
223        while( _data[i].child!=-1 ) {
224          ch=_data[i].child;
225          if( _data[ch].left_child && i==_data[ch].parent ) {
226            i=ch;
227            //break;
228          } else {
229            if( _data[ch].left_child ) {
230              child_right=_data[ch].parent;
231              _data[ch].parent = i;
232              --_data[i].degree;
233            }
234            else {
235              child_right=ch;
236              _data[i].child=-1;
237              _data[i].degree=0;
238            }
239            _data[child_right].parent = -1;
240            TreeArray[num_child] = child_right;
241            i = child_right;
242            ++num_child;
243          }
244        }
245
246        int other;
247        for( i=0; i<num_child-1; i+=2 ) {
248          if ( !_comp(_data[TreeArray[i]].prio,
249                     _data[TreeArray[i+1]].prio) ) {
250            other=TreeArray[i];
251            TreeArray[i]=TreeArray[i+1];
252            TreeArray[i+1]=other;
253          }
254          fuse( TreeArray[i], TreeArray[i+1] );
255        }
256
257        i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
258        while(i>=2) {
259          if ( _comp(_data[TreeArray[i]].prio,
260                    _data[TreeArray[i-2]].prio) ) {
261            other=TreeArray[i];
262            TreeArray[i]=TreeArray[i-2];
263            TreeArray[i-2]=other;
264          }
265          fuse( TreeArray[i-2], TreeArray[i] );
266          i-=2;
267        }
268        _min = TreeArray[0];
269      }
270
271      if ( 0==num_child ) {
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.
286    void erase (const Item& item) {
287      int i=_iim[item];
288      if ( i>=0 && _data[i].in ) {
289        decrease( item, _data[_min].prio-1 );
290        pop();
291      }
292    }
293
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.
300    void decrease (Item item, const Prio& value) {
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) ) {
310        cut(i,p);
311        if ( _comp(_data[_min].prio,value) ) {
312          fuse(_min,i);
313        } else {
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.
326    void increase (Item item, const Prio& value) {
327      erase(item);
328      push(item,value);
329    }
330
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.
339    State state(const Item &item) const {
340      int i=_iim[item];
341      if( i>=0 ) {
342        if( _data[i].in ) i=0;
343        else i=-2;
344      }
345      return State(i);
346    }
347
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.
353    /// \param i The item.
354    /// \param st The state. It should not be \c IN_HEAP.
355    void state(const Item& i, State st) {
356      switch (st) {
357      case POST_HEAP:
358      case PRE_HEAP:
359        if (state(i) == IN_HEAP) erase(i);
360        _iim[i]=st;
361        break;
362      case IN_HEAP:
363        break;
364      }
365    }
366
367  private:
368
369    void cut(int a, int b) {
370      int child_a;
371      switch (_data[a].degree) {
372        case 2:
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;
378          }
379          else {
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;
384            else
385              _data[b].child=child_a;
386          }
387          --_data[a].degree;
388          _data[_data[a].child].parent=a;
389          break;
390
391        case 1:
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;
399            }
400            else {
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;
405              else
406                _data[b].child=child_a;
407            }
408            _data[a].child=-1;
409          }
410          else {
411            --_data[b].degree;
412            if( _data[a].left_child ) {
413              _data[b].child =
414                (1==_data[b].degree) ? _data[a].parent : -1;
415            } else {
416              if (1==_data[b].degree)
417                _data[_data[b].child].parent=b;
418              else
419                _data[b].child=-1;
420            }
421          }
422          break;
423
424        case 0:
425          --_data[b].degree;
426          if( _data[a].left_child ) {
427            _data[b].child =
428              (0!=_data[b].degree) ? _data[a].parent : -1;
429          } else {
430            if( 0!=_data[b].degree )
431              _data[_data[b].child].parent=b;
432            else
433              _data[b].child=-1;
434          }
435          break;
436      }
437      _data[a].parent=-1;
438      _data[a].left_child=false;
439    }
440
441    void fuse(int a, int b) {
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;
447
448      if( -1!=child_a ) {
449        _data[b].child=child_a;
450        _data[child_a].parent=b;
451        _data[child_a].left_child=false;
452        ++_data[b].degree;
453
454        if( -1!=child_b ) {
455           _data[b].child=child_b;
456           _data[child_b].parent=child_a;
457        }
458      }
459      else { ++_data[a].degree; }
460    }
461
462    class store {
463      friend class PairingHeap;
464
465      Item name;
466      int parent;
467      int child;
468      bool left_child;
469      int degree;
470      bool in;
471      Prio prio;
472
473      store() : parent(-1), child(-1), left_child(false), degree(0), in(true) {}
474    };
475  };
476
477} //namespace lemon
478
479#endif //LEMON_PAIRING_HEAP_H
480
Note: See TracBrowser for help on using the repository browser.