# source:lemon-0.x/src/include/fib_heap.h@483:ce29ae5b2e1b

Last change on this file since 483:ce29ae5b2e1b was 477:02b8ddcb207a, checked in by Alpar Juttner, 20 years ago

doc

File size: 12.9 KB
Line
1// -*- C++ -*-
2
3#ifndef HUGO_FIB_HEAP_H
4#define HUGO_FIB_HEAP_H
5
6///ingroup auxdat
7///\file
8///\brief Fibonacci Heap implementation.
9
10#include <vector>
11#include <functional>
12#include <math.h>
13
14namespace hugo {
15
17  /// @{
18
19  /// An implementation of the Fibonacci Heap.
20
21  /**
22     This class implements the \e Fibonacci \e heap data structure. A \e heap
23     is a data structure for storing items with specified values called \e
24     priorities, such that finding the item with minimum priority with respect
25     to \e Compare is efficient. In a heap one can change the priority of an
26     item, add or erase an item, etc.
27
28     The methods \ref increase and \ref erase are not efficient in a Fibonacci
29     heap. In case of many calls to these operations, it is better to use a
30     \e binary \e heap.
31
32     \param Item The type of the items to be stored.
33     \param Prio The type of the priority of the items.
34     \param ItemIntMap A read and writable Item int map, for the usage of
35     the heap.
36     \param Compare A class for the comparison of the priorities. The
37     default is \c std::less<Prio>.
38
39  */
40
41#ifdef DOXYGEN
42  template <typename Item,
43            typename Prio,
44            typename ItemIntMap,
45            typename Compare>
46#else
47  template <typename Item,
48            typename Prio,
49            typename ItemIntMap,
50            typename Compare = std::less<Prio> >
51#endif
52  class FibHeap {
53  public:
54    typedef Prio PrioType;
55
56  private:
57    class store;
58
59    std::vector<store> container;
60    int minimum;
61    ItemIntMap &iimap;
62    Compare comp;
63    int num_items;
64
65  public:
66    enum state_enum {
67      IN_HEAP = 0,
68      PRE_HEAP = -1,
69      POST_HEAP = -2
70    };
71
72    FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
73    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
74      iimap(_iimap), comp(_comp), num_items() {}
75
76    ///The number of items stored in the heap.
77
78    /**
79       Returns the number of items stored in the heap.
80    */
81    int size() const { return num_items; }
82
83    ///Checks if the heap stores no items.
84
85    /**
86       Returns \c true iff the heap stores no items.
87    */
88    bool empty() const { return num_items==0; }
89
90    ///\c item gets to the heap with priority \c value independently if \c item was already there.
91
92    /**
93       This method calls \ref push(\c item, \c value) if \c item is not
94       stored in the heap and it calls \ref decrease(\c item, \c value) or
95       \ref increase(\c item, \c value) otherwise.
96    */
97    void set (Item const item, PrioType const value);
98
99    ///Adds \c item to the heap with priority \c value.
100
101    /**
102       Adds \c item to the heap with priority \c value.
103       \pre \c item must not be stored in the heap.
104    */
105    void push (Item const item, PrioType const value);
106
107
108    ///Returns the item having the minimum priority w.r.t.  Compare.
109
110    /**
111       This method returns the item having the minimum priority w.r.t.  Compare.
112       \pre The heap must be nonempty.
113    */
114    Item top() const { return container[minimum].name; }
115
116
117    ///Returns the minimum priority w.r.t.  Compare.
118
119    /**
120       It returns the minimum priority w.r.t.  Compare.
121       \pre The heap must be nonempty.
122    */
123    PrioType prio() const { return container[minimum].prio; }
124
125
126    ///Returns the priority of \c item.
127
128    /**
129       It returns the priority of \c item.
130       \pre \c item must be in the heap.
131    */
132    PrioType& operator[](const Item& item) {
133      return container[iimap[item]].prio;
134    }
135
136    ///Returns the priority of \c item.
137
138    /**
139       It returns the priority of \c item.
140       \pre \c item must be in the heap.
141    */
142    const PrioType& operator[](const Item& item) const {
143      return container[iimap[item]].prio;
144    }
145
146
147    ///Deletes the item with minimum priority w.r.t.  Compare.
148
149    /**
150    This method deletes the item with minimum priority w.r.t.
151    Compare from the heap.
152    \pre The heap must be non-empty.
153    */
154    void pop();
155
156    ///Deletes \c item from the heap.
157
158    /**
159       This method deletes \c item from the heap, if \c item was already
160       stored in the heap. It is quite inefficient in Fibonacci heaps.
161    */
162    void erase (const Item& item);
163
164    ///Decreases the priority of \c item to \c value.
165
166    /**
167       This method decreases the priority of \c item to \c value.
168       \pre \c item must be stored in the heap with priority at least \c
169       value w.r.t.  Compare.
170    */
171    void decrease (Item item, PrioType const value);
172
173
174    ///Increases the priority of \c item to \c value.
175
176    /**
177       This method sets the priority of \c item to \c value. Though
178       there is no precondition on the priority of \c item, this
179       method should be used only if there is a need to really \e increase
180       (w.r.t.  Compare) the priority of \c item, because this
181       method is inefficient.
182    */
183    void increase (Item item, PrioType const value) {
184      erase(item);
185      push(item, value);
186    }
187
188
189    ///Tells if \c item is in, was already in, or has never been in the heap.
190
191    /**
192       This method returns PRE_HEAP if \c item has never been in the
193       heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
194       otherwise. In the latter case it is possible that \c item will
195       get back to the heap again.
196    */
197    state_enum state(const Item &item) const {
198      int i=iimap[item];
199      if( i>=0 ) {
200        if ( container[i].in ) i=0;
201        else i=-2;
202      }
203      return state_enum(i);
204    }
205
206  private:
207
208    void balance();
209    void makeroot(int c);
210    void cut(int a, int b);
212    void fuse(int a, int b);
213    void unlace(int a);
214
215
216    class store {
217      friend class FibHeap;
218
219      Item name;
220      int parent;
221      int left_neighbor;
222      int right_neighbor;
223      int child;
224      int degree;
225      bool marked;
226      bool in;
227      PrioType prio;
228
229      store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
230    };
231  };
232
233
234
235    // **********************************************************************
236    //  IMPLEMENTATIONS
237    // **********************************************************************
238
239  template <typename Item, typename Prio, typename ItemIntMap,
240    typename Compare>
241  void FibHeap<Item, Prio, ItemIntMap, Compare>::set
242  (Item const item, PrioType const value)
243  {
244    int i=iimap[item];
245    if ( i >= 0 && container[i].in ) {
246      if ( comp(value, container[i].prio) ) decrease(item, value);
247      if ( comp(container[i].prio, value) ) increase(item, value);
248    } else push(item, value);
249  }
250
251  template <typename Item, typename Prio, typename ItemIntMap,
252    typename Compare>
253  void FibHeap<Item, Prio, ItemIntMap, Compare>::push
254  (Item const item, PrioType const value) {
255      int i=iimap[item];
256      if ( i < 0 ) {
257        int s=container.size();
258        iimap.set( item, s );
259        store st;
260        st.name=item;
261        container.push_back(st);
262        i=s;
263      } else {
264        container[i].parent=container[i].child=-1;
265        container[i].degree=0;
266        container[i].in=true;
267        container[i].marked=false;
268      }
269
270      if ( num_items ) {
271        container[container[minimum].right_neighbor].left_neighbor=i;
272        container[i].right_neighbor=container[minimum].right_neighbor;
273        container[minimum].right_neighbor=i;
274        container[i].left_neighbor=minimum;
275        if ( comp( value, container[minimum].prio) ) minimum=i;
276      } else {
277        container[i].right_neighbor=container[i].left_neighbor=i;
278        minimum=i;
279      }
280      container[i].prio=value;
281      ++num_items;
282    }
283
284  template <typename Item, typename Prio, typename ItemIntMap,
285    typename Compare>
286  void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
287      /*The first case is that there are only one root.*/
288      if ( container[minimum].left_neighbor==minimum ) {
289        container[minimum].in=false;
290        if ( container[minimum].degree!=0 ) {
291          makeroot(container[minimum].child);
292          minimum=container[minimum].child;
293          balance();
294        }
295      } else {
296        int right=container[minimum].right_neighbor;
297        unlace(minimum);
298        container[minimum].in=false;
299        if ( container[minimum].degree > 0 ) {
300          int left=container[minimum].left_neighbor;
301          int child=container[minimum].child;
302          int last_child=container[child].left_neighbor;
303
304          makeroot(child);
305
306          container[left].right_neighbor=child;
307          container[child].left_neighbor=left;
308          container[right].left_neighbor=last_child;
309          container[last_child].right_neighbor=right;
310        }
311        minimum=right;
312        balance();
313      } // the case where there are more roots
314      --num_items;
315    }
316
317
318  template <typename Item, typename Prio, typename ItemIntMap,
319    typename Compare>
320  void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
321  (const Item& item) {
322      int i=iimap[item];
323
324      if ( i >= 0 && container[i].in ) {
325        if ( container[i].parent!=-1 ) {
326          int p=container[i].parent;
327          cut(i,p);
329        }
330        minimum=i;     //As if its prio would be -infinity
331        pop();
332      }
333  }
334
335  template <typename Item, typename Prio, typename ItemIntMap,
336    typename Compare>
337  void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
338  (Item item, PrioType const value) {
339      int i=iimap[item];
340      container[i].prio=value;
341      int p=container[i].parent;
342
343      if ( p!=-1 && comp(value, container[p].prio) ) {
344        cut(i,p);
346      }
347      if ( comp(value, container[minimum].prio) ) minimum=i;
348  }
349
350
351  template <typename Item, typename Prio, typename ItemIntMap,
352    typename Compare>
353  void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
354
355    int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
356
357    std::vector<int> A(maxdeg,-1);
358
359    /*
360     *Recall that now minimum does not point to the minimum prio element.
361     *We set minimum to this during balance().
362     */
363    int anchor=container[minimum].left_neighbor;
364    int next=minimum;
365    bool end=false;
366
367       do {
368        int active=next;
369        if ( anchor==active ) end=true;
370        int d=container[active].degree;
371        next=container[active].right_neighbor;
372
373        while (A[d]!=-1) {
374          if( comp(container[active].prio, container[A[d]].prio) ) {
375            fuse(active,A[d]);
376          } else {
377            fuse(A[d],active);
378            active=A[d];
379          }
380          A[d]=-1;
381          ++d;
382        }
383        A[d]=active;
384       } while ( !end );
385
386
387       while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
388       int s=minimum;
389       int m=minimum;
390       do {
391         if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
392         s=container[s].right_neighbor;
393       } while ( s != m );
394    }
395
396  template <typename Item, typename Prio, typename ItemIntMap,
397    typename Compare>
398  void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
399  (int c) {
400      int s=c;
401      do {
402        container[s].parent=-1;
403        s=container[s].right_neighbor;
404      } while ( s != c );
405    }
406
407
408  template <typename Item, typename Prio, typename ItemIntMap,
409    typename Compare>
410  void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
411  (int a, int b) {
412    /*
413     *Replacing a from the children of b.
414     */
415    --container[b].degree;
416
417    if ( container[b].degree !=0 ) {
418      int child=container[b].child;
419      if ( child==a )
420        container[b].child=container[child].right_neighbor;
421      unlace(a);
422    }
423
424
425    /*Lacing a to the roots.*/
426    int right=container[minimum].right_neighbor;
427    container[minimum].right_neighbor=a;
428    container[a].left_neighbor=minimum;
429    container[a].right_neighbor=right;
430    container[right].left_neighbor=a;
431
432    container[a].parent=-1;
433    container[a].marked=false;
434  }
435
436
437  template <typename Item, typename Prio, typename ItemIntMap,
438    typename Compare>
439  void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
440  (int a)
441    {
442      if ( container[a].parent!=-1 ) {
443        int p=container[a].parent;
444
445        if ( container[a].marked==false ) container[a].marked=true;
446        else {
447          cut(a,p);
449        }
450      }
451    }
452
453
454  template <typename Item, typename Prio, typename ItemIntMap,
455    typename Compare>
456  void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
457  (int a, int b) {
458      unlace(b);
459
460      /*Lacing b under a.*/
461      container[b].parent=a;
462
463      if (container[a].degree==0) {
464        container[b].left_neighbor=b;
465        container[b].right_neighbor=b;
466        container[a].child=b;
467      } else {
468        int child=container[a].child;
469        int last_child=container[child].left_neighbor;
470        container[child].left_neighbor=b;
471        container[b].right_neighbor=child;
472        container[last_child].right_neighbor=b;
473        container[b].left_neighbor=last_child;
474      }
475
476      ++container[a].degree;
477
478      container[b].marked=false;
479    }
480
481
482  /*
483   *It is invoked only if a has siblings.
484   */
485  template <typename Item, typename Prio, typename ItemIntMap,
486    typename Compare>
487  void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
488  (int a) {
489      int leftn=container[a].left_neighbor;
490      int rightn=container[a].right_neighbor;
491      container[leftn].right_neighbor=rightn;
492      container[rightn].left_neighbor=leftn;
493  }
494
495  ///@}
496
497} //namespace hugo
498
499#endif //HUGO_FIB_HEAP_H
500
Note: See TracBrowser for help on using the repository browser.