COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/bin_heap.h @ 1284:b941d044f87b

Last change on this file since 1284:b941d044f87b was 1270:806451fd084b, checked in by jacint, 15 years ago

bugfixes in doc

File size: 8.4 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/bin_heap.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17#ifndef LEMON_BIN_HEAP_H
18#define LEMON_BIN_HEAP_H
19
20///\ingroup auxdat
21///\file
22///\brief Binary Heap implementation.
23
24#include <vector>
25#include <utility>
26#include <functional>
27
28namespace lemon {
29
30  /// \addtogroup auxdat
31  /// @{
32
33  /// A Binary Heap implementation.
34 
35  ///This class implements the \e binary \e heap data structure. A \e heap
36  ///is a data structure for storing items with specified values called \e
37  ///priorities in such a way that finding the item with minimum priority is
38  ///efficient. \c Compare specifies the ordering of the priorities. In a heap
39  ///one can change the priority of an item, add or erase an item, etc.
40  ///
41  ///\param Item Type of the items to be stored. 
42  ///\param Prio Type of the priority of the items.
43  ///\param ItemIntMap A read and writable Item int map, used internally
44  ///to handle the cross references.
45  ///\param 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 Item, typename Prio, typename ItemIntMap,
51            typename Compare = std::less<Prio> >
52  class BinHeap {
53
54  public:
55    typedef Item                             ItemType;
56    // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
57    typedef Prio                             PrioType;
58    typedef std::pair<ItemType,PrioType>     PairType;
59    typedef ItemIntMap                       ItemIntMapType;
60    typedef Compare                          PrioCompare;
61
62    /**
63     * Each Item element have a state associated to it. It may be "in heap",
64     * "pre heap" or "post heap". The later two are indifferent from the
65     * heap's point of view, but may be useful to the user.
66     *
67     * The ItemIntMap _should_ be initialized in such way, that it maps
68     * PRE_HEAP (-1) to any element to be put in the heap...
69     */
70    ///\todo it is used nowhere
71    ///
72    enum state_enum {
73      IN_HEAP = 0,
74      PRE_HEAP = -1,
75      POST_HEAP = -2
76    };
77
78  private:
79    std::vector<PairType> data;
80    Compare comp;
81    // FIXME: jo ez igy???
82    ItemIntMap &iim;
83
84  public:
85    ///The constructor
86
87    /**
88       \c _iim should be given to the constructor, since it is used
89       internally to handle the cross references.
90    */
91    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
92   
93    ///The constructor
94
95    /**
96       \c _iim should be given to the constructor, since it is used
97       internally to handle the cross references. \c _comp is an
98       object for ordering of the priorities.
99    */
100    BinHeap(ItemIntMap &_iim, const Compare &_comp)
101      : iim(_iim), comp(_comp) {}
102
103
104    ///The number of items stored in the heap.
105
106    /**
107       Returns the number of items stored in the heap.
108    */
109    int size() const { return data.size(); }
110   
111    ///Checks if the heap stores no items.
112   
113    /**
114       Returns \c true if and only if the heap stores no items.
115    */
116    bool empty() const { return data.empty(); }
117
118  private:
119    static int parent(int i) { return (i-1)/2; }
120    static int second_child(int i) { return 2*i+2; }
121    bool less(const PairType &p1, const PairType &p2) const {
122      return comp(p1.second, p2.second);
123    }
124
125    int bubble_up(int hole, PairType p);
126    int bubble_down(int hole, PairType p, int length);
127
128    void move(const PairType &p, int i) {
129      data[i] = p;
130      iim.set(p.first, i);
131    }
132
133    void rmidx(int h) {
134      int n = data.size()-1;
135      if( h>=0 && h<=n ) {
136        iim.set(data[h].first, POST_HEAP);
137        if ( h<n ) {
138          bubble_down(h, data[n], n);
139        }
140        data.pop_back();
141      }
142    }
143
144  public:
145    ///Adds \c p.first to the heap with priority \c p.second.
146   
147    /**
148       Adds \c p.first to the heap with priority \c p.second.
149       \c p.first must not be stored in the heap.
150    */
151    void push(const PairType &p) {
152      int n = data.size();
153      data.resize(n+1);
154      bubble_up(n, p);
155    }
156
157    ///Adds \c i to the heap with priority \c p.
158   
159    /**
160       Adds \c i to the heap with priority \c p.
161       \pre \c i must not be stored in the heap.
162    */
163    void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
164
165    ///Returns the item with minimum priority relative to \c Compare.
166   
167    /**
168       This method returns the item with minimum priority relative to \c
169       Compare. 
170       \pre The heap must be nonempty. 
171    */
172    Item top() const {
173      return data[0].first;
174    }
175
176    ///Returns the minimum priority relative to \c Compare.
177
178    /**
179       It returns the minimum priority relative to \c Compare.
180       \pre The heap must be nonempty.
181    */
182    Prio prio() const {
183      return data[0].second;
184    }
185
186    ///Deletes the item with minimum priority relative to \c Compare.
187
188    /**
189    This method deletes the item with minimum priority relative to \c
190    Compare from the heap. 
191    \pre The heap must be non-empty. 
192    */
193    void pop() {
194      rmidx(0);
195    }
196
197    ///Deletes \c i from the heap.
198
199    /**
200       This method deletes item \c i from the heap, if \c i was
201       already stored in the heap.
202    */
203    void erase(const Item &i) {
204      rmidx(iim[i]);
205    }
206
207   
208    ///Returns the priority of \c i.
209
210    /**
211       This function returns the priority of item \c i. 
212       \pre \c i must be in the heap.
213    */
214    Prio operator[](const Item &i) const {
215      int idx = iim[i];
216      return data[idx].second;
217    }
218
219    ///\c i gets to the heap with priority \c p independently if \c i was already there.
220
221    /**
222       This method calls \ref push(\c i, \c p) if \c i is not stored
223       in the heap and sets the priority of \c i to \c p otherwise.
224    */
225    void set(const Item &i, const Prio &p) {
226      int idx = iim[i];
227      if( idx < 0 ) {
228        push(i,p);
229      }
230      else if( comp(p, data[idx].second) ) {
231        bubble_up(idx, PairType(i,p));
232      }
233      else {
234        bubble_down(idx, PairType(i,p), data.size());
235      }
236    }
237
238    ///Decreases the priority of \c i to \c p.
239
240    /**
241       This method decreases the priority of item \c i to \c p.
242       \pre \c i must be stored in the heap with priority at least \c
243       p relative to \c Compare.
244    */
245    void decrease(const Item &i, const Prio &p) {
246      int idx = iim[i];
247      bubble_up(idx, PairType(i,p));
248    }
249   
250    ///Increases the priority of \c i to \c p.
251
252    /**
253       This method sets the priority of item \c i to \c p.
254       \pre \c i must be stored in the heap with priority at most \c
255       p relative to \c Compare.
256    */
257    void increase(const Item &i, const Prio &p) {
258      int idx = iim[i];
259      bubble_down(idx, PairType(i,p), data.size());
260    }
261
262    ///Returns if \c item is in, has already been in, or has never been in the heap.
263
264    /**
265       This method returns PRE_HEAP if \c item has never been in the
266       heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
267       otherwise. In the latter case it is possible that \c item will
268       get back to the heap again.
269    */
270    state_enum state(const Item &i) const {
271      int s = iim[i];
272      if( s>=0 )
273        s=0;
274      return state_enum(s);
275    }
276
277  }; // class BinHeap
278
279 
280  template <typename K, typename V, typename M, typename C>
281  int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
282    int par = parent(hole);
283    while( hole>0 && less(p,data[par]) ) {
284      move(data[par],hole);
285      hole = par;
286      par = parent(hole);
287    }
288    move(p, hole);
289    return hole;
290  }
291
292  template <typename K, typename V, typename M, typename C>
293  int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
294    int child = second_child(hole);
295    while(child < length) {
296      if( less(data[child-1], data[child]) ) {
297        --child;
298      }
299      if( !less(data[child], p) )
300        goto ok;
301      move(data[child], hole);
302      hole = child;
303      child = second_child(hole);
304    }
305    child--;
306    if( child<length && less(data[child], p) ) {
307      move(data[child], hole);
308      hole=child;
309    }
310  ok:
311    move(p, hole);
312    return hole;
313  }
314
315  ///@}
316
317} // namespace lemon
318
319#endif // LEMON_BIN_HEAP_H
Note: See TracBrowser for help on using the repository browser.