COIN-OR::LEMON - Graph Library

source: lemon/lemon/bin_heap.h @ 912:37f440367057

1.1
Last change on this file since 912:37f440367057 was 912:37f440367057, checked in by Alpar Juttner <alpar@…>, 10 years ago

Back out 4 changesets (#50, #312)

File size: 10.1 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[100]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[100]4 *
[463]5 * Copyright (C) 2003-2009
[100]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_BIN_HEAP_H
20#define LEMON_BIN_HEAP_H
21
22///\ingroup auxdat
23///\file
24///\brief Binary Heap implementation.
25
26#include <vector>
27#include <utility>
28#include <functional>
29
30namespace lemon {
31
32  ///\ingroup auxdat
33  ///
34  ///\brief A Binary Heap implementation.
35  ///
[912]36  ///This class implements the \e binary \e heap data structure.
37  ///
[606]38  ///A \e heap is a data structure for storing items with specified values
39  ///called \e priorities in such a way that finding the item with minimum
[912]40  ///priority is efficient. \c Comp specifies the ordering of the priorities.
[606]41  ///In a heap one can change the priority of an item, add or erase an
42  ///item, etc.
[100]43  ///
[606]44  ///\tparam PR Type of the priority of the items.
45  ///\tparam IM A read and writable item map with int values, used internally
[100]46  ///to handle the cross references.
[912]47  ///\tparam Comp A functor class for the ordering of the priorities.
[606]48  ///The default is \c std::less<PR>.
[100]49  ///
50  ///\sa FibHeap
51  ///\sa Dijkstra
[912]52  template <typename PR, typename IM, typename Comp = std::less<PR> >
[100]53  class BinHeap {
54
55  public:
56    ///\e
[606]57    typedef IM ItemIntMap;
[100]58    ///\e
[606]59    typedef PR Prio;
[100]60    ///\e
61    typedef typename ItemIntMap::Key Item;
62    ///\e
63    typedef std::pair<Item,Prio> Pair;
64    ///\e
[912]65    typedef Comp Compare;
[100]66
67    /// \brief Type to represent the items states.
68    ///
69    /// Each Item element have a state associated to it. It may be "in heap",
70    /// "pre heap" or "post heap". The latter two are indifferent from the
71    /// heap's point of view, but may be useful to the user.
72    ///
[606]73    /// The item-int map must be initialized in such way that it assigns
74    /// \c PRE_HEAP (<tt>-1</tt>) to any element to be put in the heap.
[100]75    enum State {
[631]76      IN_HEAP = 0,    ///< = 0.
77      PRE_HEAP = -1,  ///< = -1.
78      POST_HEAP = -2  ///< = -2.
[100]79    };
80
81  private:
[606]82    std::vector<Pair> _data;
83    Compare _comp;
84    ItemIntMap &_iim;
[100]85
86  public:
87    /// \brief The constructor.
88    ///
89    /// The constructor.
[606]90    /// \param map should be given to the constructor, since it is used
[100]91    /// internally to handle the cross references. The value of the map
[606]92    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
93    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
[209]94
[100]95    /// \brief The constructor.
96    ///
97    /// The constructor.
[606]98    /// \param map should be given to the constructor, since it is used
[100]99    /// internally to handle the cross references. The value of the map
100    /// should be PRE_HEAP (-1) for each element.
101    ///
[606]102    /// \param comp The comparator function object.
103    BinHeap(ItemIntMap &map, const Compare &comp)
104      : _iim(map), _comp(comp) {}
[100]105
106
107    /// The number of items stored in the heap.
108    ///
109    /// \brief Returns the number of items stored in the heap.
[606]110    int size() const { return _data.size(); }
[209]111
[100]112    /// \brief Checks if the heap stores no items.
113    ///
114    /// Returns \c true if and only if the heap stores no items.
[606]115    bool empty() const { return _data.empty(); }
[100]116
117    /// \brief Make empty this heap.
[209]118    ///
[100]119    /// Make empty this heap. It does not change the cross reference map.
120    /// If you want to reuse what is not surely empty you should first clear
121    /// the heap and after that you should set the cross reference map for
122    /// each item to \c PRE_HEAP.
[209]123    void clear() {
[606]124      _data.clear();
[100]125    }
126
127  private:
128    static int parent(int i) { return (i-1)/2; }
129
130    static int second_child(int i) { return 2*i+2; }
131    bool less(const Pair &p1, const Pair &p2) const {
[606]132      return _comp(p1.second, p2.second);
[100]133    }
134
135    int bubble_up(int hole, Pair p) {
136      int par = parent(hole);
[606]137      while( hole>0 && less(p,_data[par]) ) {
138        move(_data[par],hole);
[209]139        hole = par;
140        par = parent(hole);
[100]141      }
142      move(p, hole);
143      return hole;
144    }
145
146    int bubble_down(int hole, Pair p, int length) {
147      int child = second_child(hole);
148      while(child < length) {
[606]149        if( less(_data[child-1], _data[child]) ) {
[209]150          --child;
151        }
[606]152        if( !less(_data[child], p) )
[209]153          goto ok;
[606]154        move(_data[child], hole);
[209]155        hole = child;
156        child = second_child(hole);
[100]157      }
158      child--;
[606]159      if( child<length && less(_data[child], p) ) {
160        move(_data[child], hole);
[209]161        hole=child;
[100]162      }
163    ok:
164      move(p, hole);
165      return hole;
166    }
167
168    void move(const Pair &p, int i) {
[606]169      _data[i] = p;
170      _iim.set(p.first, i);
[100]171    }
172
173  public:
174    /// \brief Insert a pair of item and priority into the heap.
175    ///
176    /// Adds \c p.first to the heap with priority \c p.second.
177    /// \param p The pair to insert.
178    void push(const Pair &p) {
[606]179      int n = _data.size();
180      _data.resize(n+1);
[100]181      bubble_up(n, p);
182    }
183
184    /// \brief Insert an item into the heap with the given heap.
[209]185    ///
186    /// Adds \c i to the heap with priority \c p.
[100]187    /// \param i The item to insert.
188    /// \param p The priority of the item.
189    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
190
191    /// \brief Returns the item with minimum priority relative to \c Compare.
192    ///
193    /// This method returns the item with minimum priority relative to \c
[209]194    /// Compare.
195    /// \pre The heap must be nonempty.
[100]196    Item top() const {
[606]197      return _data[0].first;
[100]198    }
199
200    /// \brief Returns the minimum priority relative to \c Compare.
201    ///
202    /// It returns the minimum priority relative to \c Compare.
203    /// \pre The heap must be nonempty.
204    Prio prio() const {
[606]205      return _data[0].second;
[100]206    }
207
208    /// \brief Deletes the item with minimum priority relative to \c Compare.
209    ///
210    /// This method deletes the item with minimum priority relative to \c
[209]211    /// Compare from the heap.
212    /// \pre The heap must be non-empty.
[100]213    void pop() {
[606]214      int n = _data.size()-1;
215      _iim.set(_data[0].first, POST_HEAP);
[100]216      if (n > 0) {
[606]217        bubble_down(0, _data[n], n);
[100]218      }
[606]219      _data.pop_back();
[100]220    }
221
222    /// \brief Deletes \c i from the heap.
223    ///
224    /// This method deletes item \c i from the heap.
225    /// \param i The item to erase.
226    /// \pre The item should be in the heap.
227    void erase(const Item &i) {
[606]228      int h = _iim[i];
229      int n = _data.size()-1;
230      _iim.set(_data[h].first, POST_HEAP);
[100]231      if( h < n ) {
[606]232        if ( bubble_up(h, _data[n]) == h) {
233          bubble_down(h, _data[n], n);
[209]234        }
[100]235      }
[606]236      _data.pop_back();
[100]237    }
238
[209]239
[100]240    /// \brief Returns the priority of \c i.
241    ///
[209]242    /// This function returns the priority of item \c i.
[606]243    /// \param i The item.
[100]244    /// \pre \c i must be in the heap.
245    Prio operator[](const Item &i) const {
[606]246      int idx = _iim[i];
247      return _data[idx].second;
[100]248    }
249
[209]250    /// \brief \c i gets to the heap with priority \c p independently
[100]251    /// if \c i was already there.
252    ///
253    /// This method calls \ref push(\c i, \c p) if \c i is not stored
254    /// in the heap and sets the priority of \c i to \c p otherwise.
255    /// \param i The item.
256    /// \param p The priority.
257    void set(const Item &i, const Prio &p) {
[606]258      int idx = _iim[i];
[100]259      if( idx < 0 ) {
[209]260        push(i,p);
[100]261      }
[606]262      else if( _comp(p, _data[idx].second) ) {
[209]263        bubble_up(idx, Pair(i,p));
[100]264      }
265      else {
[606]266        bubble_down(idx, Pair(i,p), _data.size());
[100]267      }
268    }
269
270    /// \brief Decreases the priority of \c i to \c p.
271    ///
272    /// This method decreases the priority of item \c i to \c p.
[606]273    /// \param i The item.
274    /// \param p The priority.
[100]275    /// \pre \c i must be stored in the heap with priority at least \c
276    /// p relative to \c Compare.
277    void decrease(const Item &i, const Prio &p) {
[606]278      int idx = _iim[i];
[100]279      bubble_up(idx, Pair(i,p));
280    }
[209]281
[100]282    /// \brief Increases the priority of \c i to \c p.
283    ///
[209]284    /// This method sets the priority of item \c i to \c p.
[606]285    /// \param i The item.
286    /// \param p The priority.
[100]287    /// \pre \c i must be stored in the heap with priority at most \c
288    /// p relative to \c Compare.
289    void increase(const Item &i, const Prio &p) {
[606]290      int idx = _iim[i];
291      bubble_down(idx, Pair(i,p), _data.size());
[100]292    }
293
[209]294    /// \brief Returns if \c item is in, has already been in, or has
[100]295    /// never been in the heap.
296    ///
297    /// This method returns PRE_HEAP if \c item has never been in the
298    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
299    /// otherwise. In the latter case it is possible that \c item will
300    /// get back to the heap again.
301    /// \param i The item.
302    State state(const Item &i) const {
[606]303      int s = _iim[i];
[100]304      if( s>=0 )
[209]305        s=0;
[100]306      return State(s);
307    }
308
309    /// \brief Sets the state of the \c item in the heap.
310    ///
311    /// Sets the state of the \c item in the heap. It can be used to
312    /// manually clear the heap when it is important to achive the
313    /// better time complexity.
314    /// \param i The item.
[209]315    /// \param st The state. It should not be \c IN_HEAP.
[100]316    void state(const Item& i, State st) {
317      switch (st) {
318      case POST_HEAP:
319      case PRE_HEAP:
320        if (state(i) == IN_HEAP) {
321          erase(i);
322        }
[606]323        _iim[i] = st;
[100]324        break;
325      case IN_HEAP:
326        break;
327      }
328    }
329
330    /// \brief Replaces an item in the heap.
331    ///
332    /// The \c i item is replaced with \c j item. The \c i item should
333    /// be in the heap, while the \c j should be out of the heap. The
334    /// \c i item will out of the heap and \c j will be in the heap
335    /// with the same prioriority as prevoiusly the \c i item.
336    void replace(const Item& i, const Item& j) {
[606]337      int idx = _iim[i];
338      _iim.set(i, _iim[j]);
339      _iim.set(j, idx);
340      _data[idx].first = j;
[100]341    }
342
343  }; // class BinHeap
[209]344
[100]345} // namespace lemon
346
347#endif // LEMON_BIN_HEAP_H
Note: See TracBrowser for help on using the repository browser.