COIN-OR::LEMON - Graph Library

source: lemon/lemon/kary_heap.h @ 748:d1a9224f1e30

Last change on this file since 748:d1a9224f1e30 was 748:d1a9224f1e30, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Add fourary, k-ary, pairing and binomial heaps (#301)
These structures were implemented by Dorian Batha.

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