COIN-OR::LEMON - Graph Library

source: lemon/lemon/bin_heap.h @ 726:9c7639f3a741

Last change on this file since 726:9c7639f3a741 was 631:33c6b6e755cd, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Small doc improvements (#263)

File size: 10.1 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_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  ///
36  ///This class implements the \e binary \e heap data structure.
37  ///
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
40  ///priority is efficient. \c Comp specifies the ordering of the priorities.
41  ///In a heap one can change the priority of an item, add or erase an
42  ///item, etc.
43  ///
44  ///\tparam PR Type of the priority of the items.
45  ///\tparam IM A read and writable item map with int values, used internally
46  ///to handle the cross references.
47  ///\tparam Comp A functor class for the ordering of the priorities.
48  ///The default is \c std::less<PR>.
49  ///
50  ///\sa FibHeap
51  ///\sa Dijkstra
52  template <typename PR, typename IM, typename Comp = std::less<PR> >
53  class BinHeap {
54
55  public:
56    ///\e
57    typedef IM ItemIntMap;
58    ///\e
59    typedef PR Prio;
60    ///\e
61    typedef typename ItemIntMap::Key Item;
62    ///\e
63    typedef std::pair<Item,Prio> Pair;
64    ///\e
65    typedef Comp Compare;
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    ///
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.
75    enum State {
76      IN_HEAP = 0,    ///< = 0.
77      PRE_HEAP = -1,  ///< = -1.
78      POST_HEAP = -2  ///< = -2.
79    };
80
81  private:
82    std::vector<Pair> _data;
83    Compare _comp;
84    ItemIntMap &_iim;
85
86  public:
87    /// \brief The constructor.
88    ///
89    /// The constructor.
90    /// \param map should be given to the constructor, since it is used
91    /// internally to handle the cross references. The value of the map
92    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
93    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
94
95    /// \brief The constructor.
96    ///
97    /// The constructor.
98    /// \param map should be given to the constructor, since it is used
99    /// internally to handle the cross references. The value of the map
100    /// should be PRE_HEAP (-1) for each element.
101    ///
102    /// \param comp The comparator function object.
103    BinHeap(ItemIntMap &map, const Compare &comp)
104      : _iim(map), _comp(comp) {}
105
106
107    /// The number of items stored in the heap.
108    ///
109    /// \brief Returns the number of items stored in the heap.
110    int size() const { return _data.size(); }
111
112    /// \brief Checks if the heap stores no items.
113    ///
114    /// Returns \c true if and only if the heap stores no items.
115    bool empty() const { return _data.empty(); }
116
117    /// \brief Make empty this heap.
118    ///
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.
123    void clear() {
124      _data.clear();
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 {
132      return _comp(p1.second, p2.second);
133    }
134
135    int bubble_up(int hole, Pair p) {
136      int par = parent(hole);
137      while( hole>0 && less(p,_data[par]) ) {
138        move(_data[par],hole);
139        hole = par;
140        par = parent(hole);
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) {
149        if( less(_data[child-1], _data[child]) ) {
150          --child;
151        }
152        if( !less(_data[child], p) )
153          goto ok;
154        move(_data[child], hole);
155        hole = child;
156        child = second_child(hole);
157      }
158      child--;
159      if( child<length && less(_data[child], p) ) {
160        move(_data[child], hole);
161        hole=child;
162      }
163    ok:
164      move(p, hole);
165      return hole;
166    }
167
168    void move(const Pair &p, int i) {
169      _data[i] = p;
170      _iim.set(p.first, i);
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) {
179      int n = _data.size();
180      _data.resize(n+1);
181      bubble_up(n, p);
182    }
183
184    /// \brief Insert an item into the heap with the given heap.
185    ///
186    /// Adds \c i to the heap with priority \c p.
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
194    /// Compare.
195    /// \pre The heap must be nonempty.
196    Item top() const {
197      return _data[0].first;
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 {
205      return _data[0].second;
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
211    /// Compare from the heap.
212    /// \pre The heap must be non-empty.
213    void pop() {
214      int n = _data.size()-1;
215      _iim.set(_data[0].first, POST_HEAP);
216      if (n > 0) {
217        bubble_down(0, _data[n], n);
218      }
219      _data.pop_back();
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) {
228      int h = _iim[i];
229      int n = _data.size()-1;
230      _iim.set(_data[h].first, POST_HEAP);
231      if( h < n ) {
232        if ( bubble_up(h, _data[n]) == h) {
233          bubble_down(h, _data[n], n);
234        }
235      }
236      _data.pop_back();
237    }
238
239
240    /// \brief Returns the priority of \c i.
241    ///
242    /// This function returns the priority of item \c i.
243    /// \param i The item.
244    /// \pre \c i must be in the heap.
245    Prio operator[](const Item &i) const {
246      int idx = _iim[i];
247      return _data[idx].second;
248    }
249
250    /// \brief \c i gets to the heap with priority \c p independently
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) {
258      int idx = _iim[i];
259      if( idx < 0 ) {
260        push(i,p);
261      }
262      else if( _comp(p, _data[idx].second) ) {
263        bubble_up(idx, Pair(i,p));
264      }
265      else {
266        bubble_down(idx, Pair(i,p), _data.size());
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.
273    /// \param i The item.
274    /// \param p The priority.
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) {
278      int idx = _iim[i];
279      bubble_up(idx, Pair(i,p));
280    }
281
282    /// \brief Increases the priority of \c i to \c p.
283    ///
284    /// This method sets the priority of item \c i to \c p.
285    /// \param i The item.
286    /// \param p The priority.
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) {
290      int idx = _iim[i];
291      bubble_down(idx, Pair(i,p), _data.size());
292    }
293
294    /// \brief Returns if \c item is in, has already been in, or has
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 {
303      int s = _iim[i];
304      if( s>=0 )
305        s=0;
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.
315    /// \param st The state. It should not be \c IN_HEAP.
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        }
323        _iim[i] = st;
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) {
337      int idx = _iim[i];
338      _iim.set(i, _iim[j]);
339      _iim.set(j, idx);
340      _data[idx].first = j;
341    }
342
343  }; // class BinHeap
344
345} // namespace lemon
346
347#endif // LEMON_BIN_HEAP_H
Note: See TracBrowser for help on using the repository browser.