COIN-OR::LEMON - Graph Library

source: lemon/lemon/pairing_heap.h @ 969:6dd226d3dcba

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

Small improvements in heap implementations (#301)

File size: 13.7 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      std::vector<int> trees;
212      int i=0, child_right = 0;
213      _data[_min].in=false;
214
215      if( -1!=_data[_min].child ) {
216        i=_data[_min].child;
217        trees.push_back(i);
218        _data[i].parent = -1;
219        _data[_min].child = -1;
220
221        int ch=-1;
222        while( _data[i].child!=-1 ) {
223          ch=_data[i].child;
224          if( _data[ch].left_child && i==_data[ch].parent ) {
225            break;
226          } else {
227            if( _data[ch].left_child ) {
228              child_right=_data[ch].parent;
229              _data[ch].parent = i;
230              --_data[i].degree;
231            }
232            else {
233              child_right=ch;
234              _data[i].child=-1;
235              _data[i].degree=0;
236            }
237            _data[child_right].parent = -1;
238            trees.push_back(child_right);
239            i = child_right;
240          }
241        }
242
243        int num_child = trees.size();
244        int other;
245        for( i=0; i<num_child-1; i+=2 ) {
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;
250          }
251          fuse( trees[i], trees[i+1] );
252        }
253
254        i = (0==(num_child % 2)) ? num_child-2 : num_child-1;
255        while(i>=2) {
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;
260          }
261          fuse( trees[i-2], trees[i] );
262          i-=2;
263        }
264        _min = trees[0];
265      }
266      else {
267        _min = _data[_min].child;
268      }
269
270      if (_min >= 0) _data[_min].left_child = false;
271      --_num_items;
272    }
273
274    /// \brief Remove the given item from the heap.
275    ///
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.
280    void erase (const Item& item) {
281      int i=_iim[item];
282      if ( i>=0 && _data[i].in ) {
283        decrease( item, _data[_min].prio-1 );
284        pop();
285      }
286    }
287
288    /// \brief Decrease the priority of an item to the given value.
289    ///
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.
294    void decrease (Item item, const Prio& value) {
295      int i=_iim[item];
296      _data[i].prio=value;
297      int p=_data[i].parent;
298
299      if( _data[i].left_child && i!=_data[p].child ) {
300        p=_data[p].parent;
301      }
302
303      if ( p!=-1 && _comp(value,_data[p].prio) ) {
304        cut(i,p);
305        if ( _comp(_data[_min].prio,value) ) {
306          fuse(_min,i);
307        } else {
308          fuse(i,_min);
309          _min=i;
310        }
311      }
312    }
313
314    /// \brief Increase the priority of an item to the given value.
315    ///
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.
320    void increase (Item item, const Prio& value) {
321      erase(item);
322      push(item,value);
323    }
324
325    /// \brief Return the state of an item.
326    ///
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.
333    State state(const Item &item) const {
334      int i=_iim[item];
335      if( i>=0 ) {
336        if( _data[i].in ) i=0;
337        else i=-2;
338      }
339      return State(i);
340    }
341
342    /// \brief Set the state of an item in the heap.
343    ///
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.
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);
354        _iim[i]=st;
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;
365      switch (_data[a].degree) {
366        case 2:
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;
372          }
373          else {
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;
378            else
379              _data[b].child=child_a;
380          }
381          --_data[a].degree;
382          _data[_data[a].child].parent=a;
383          break;
384
385        case 1:
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;
393            }
394            else {
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;
399              else
400                _data[b].child=child_a;
401            }
402            _data[a].child=-1;
403          }
404          else {
405            --_data[b].degree;
406            if( _data[a].left_child ) {
407              _data[b].child =
408                (1==_data[b].degree) ? _data[a].parent : -1;
409            } else {
410              if (1==_data[b].degree)
411                _data[_data[b].child].parent=b;
412              else
413                _data[b].child=-1;
414            }
415          }
416          break;
417
418        case 0:
419          --_data[b].degree;
420          if( _data[a].left_child ) {
421            _data[b].child =
422              (0!=_data[b].degree) ? _data[a].parent : -1;
423          } else {
424            if( 0!=_data[b].degree )
425              _data[_data[b].child].parent=b;
426            else
427              _data[b].child=-1;
428          }
429          break;
430      }
431      _data[a].parent=-1;
432      _data[a].left_child=false;
433    }
434
435    void fuse(int a, int b) {
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;
441
442      if( -1!=child_a ) {
443        _data[b].child=child_a;
444        _data[child_a].parent=b;
445        _data[child_a].left_child=false;
446        ++_data[b].degree;
447
448        if( -1!=child_b ) {
449           _data[b].child=child_b;
450           _data[child_b].parent=child_a;
451        }
452      }
453      else { ++_data[a].degree; }
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.