COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bin_heap.h @ 2086:3fc072264f77

Last change on this file since 2086:3fc072264f77 was 2050:d9a221218ea4, checked in by Balazs Dezso, 18 years ago

Changing the mining of the clear in heaps
It does not touch the heap cross ref. It is
sometimes more clean useable and more efficient

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