COIN-OR::LEMON - Graph Library

source: lemon/lemon/bin_heap.h @ 209:765619b7cbb2

Last change on this file since 209:765619b7cbb2 was 209:765619b7cbb2, checked in by Alpar Juttner <alpar@…>, 16 years ago

Apply unify-sources.sh to the source tree

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