COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bin_heap.h @ 1902:e9af75c90c28

Last change on this file since 1902:e9af75c90c28 was 1902:e9af75c90c28, checked in by Balazs Dezso, 14 years ago

state setting function for heaps

If we know that which elements were in the heap then
we can clear it in better time complexity.

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