COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/fourary_heap.h @ 702:bdc7dfc8c054

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