EXAMPLE_PATH is set to the demo dir.
3 #ifndef HUGO_FIB_HEAP_H
4 #define HUGO_FIB_HEAP_H
8 ///\brief Fibonacci Heap implementation.
16 /// \addtogroup auxdat
21 ///This class implements the \e Fibonacci \e heap data structure. A \e heap
22 ///is a data structure for storing items with specified values called \e
23 ///priorities in such a way that finding the item with minimum priority is
24 ///efficient. \ref Compare specifies the ordering of the priorities. In a heap
25 ///one can change the priority of an item, add or erase an item, etc.
27 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
28 ///heap. In case of many calls to these operations, it is better to use a
31 ///\param Item Type of the items to be stored.
32 ///\param Prio Type of the priority of the items.
33 ///\param ItemIntMap A read and writable Item int map, for the usage of
35 ///\param Compare A class for the ordering of the priorities. The
36 ///default is \c std::less<Prio>.
38 ///\author Jacint Szabo
41 template <typename Item,
46 template <typename Item,
49 typename Compare = std::less<Prio> >
53 typedef Prio PrioType;
58 std::vector<store> container;
71 FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
72 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
73 iimap(_iimap), comp(_comp), num_items() {}
75 ///The number of items stored in the heap.
78 Returns the number of items stored in the heap.
80 int size() const { return num_items; }
82 ///Checks if the heap stores no items.
85 Returns \c true if and only if the heap stores no items.
87 bool empty() const { return num_items==0; }
89 ///\c item gets to the heap with priority \c value independently if \c item was already there.
92 This method calls \ref push(\c item, \c value) if \c item is not
93 stored in the heap and it calls \ref decrease(\c item, \c value) or
94 \ref increase(\c item, \c value) otherwise.
96 void set (Item const item, PrioType const value);
98 ///Adds \c item to the heap with priority \c value.
101 Adds \c item to the heap with priority \c value.
102 \pre \c item must not be stored in the heap.
104 void push (Item const item, PrioType const value);
106 ///Returns the item with minimum priority relative to \ref Compare.
109 This method returns the item with minimum priority relative to \ref
111 \pre The heap must be nonempty.
113 Item top() const { return container[minimum].name; }
115 ///Returns the minimum priority relative to \ref Compare.
118 It returns the minimum priority relative to \ref Compare.
119 \pre The heap must be nonempty.
121 PrioType prio() const { return container[minimum].prio; }
123 ///Returns the priority of \c item.
126 This function returns the priority of \c item.
127 \pre \c item must be in the heap.
129 PrioType& operator[](const Item& item) {
130 return container[iimap[item]].prio;
133 ///Returns the priority of \c item.
136 It returns the priority of \c item.
137 \pre \c item must be in the heap.
139 const PrioType& operator[](const Item& item) const {
140 return container[iimap[item]].prio;
144 ///Deletes the item with minimum priority relative to \ref Compare.
147 This method deletes the item with minimum priority relative to \ref
148 Compare from the heap.
149 \pre The heap must be non-empty.
153 ///Deletes \c item from the heap.
156 This method deletes \c item from the heap, if \c item was already
157 stored in the heap. It is quite inefficient in Fibonacci heaps.
159 void erase (const Item& item);
161 ///Decreases the priority of \c item to \c value.
164 This method decreases the priority of \c item to \c value.
165 \pre \c item must be stored in the heap with priority at least \c
166 value relative to \ref Compare.
168 void decrease (Item item, PrioType const value);
170 ///Increases the priority of \c item to \c value.
173 This method sets the priority of \c item to \c value. Though
174 there is no precondition on the priority of \c item, this
175 method should be used only if it is indeed necessary to increase
176 (relative to \ref Compare) the priority of \c item, because this
177 method is inefficient.
179 void increase (Item item, PrioType const value) {
185 ///Returns if \c item is in, has already been in, or has never been in the heap.
188 This method returns PRE_HEAP if \c item has never been in the
189 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
190 otherwise. In the latter case it is possible that \c item will
191 get back to the heap again.
193 state_enum state(const Item &item) const {
196 if ( container[i].in ) i=0;
199 return state_enum(i);
205 void makeroot(int c);
206 void cut(int a, int b);
208 void fuse(int a, int b);
213 friend class FibHeap;
225 store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
231 // **********************************************************************
233 // **********************************************************************
235 template <typename Item, typename Prio, typename ItemIntMap,
237 void FibHeap<Item, Prio, ItemIntMap, Compare>::set
238 (Item const item, PrioType const value)
241 if ( i >= 0 && container[i].in ) {
242 if ( comp(value, container[i].prio) ) decrease(item, value);
243 if ( comp(container[i].prio, value) ) increase(item, value);
244 } else push(item, value);
247 template <typename Item, typename Prio, typename ItemIntMap,
249 void FibHeap<Item, Prio, ItemIntMap, Compare>::push
250 (Item const item, PrioType const value) {
253 int s=container.size();
254 iimap.set( item, s );
257 container.push_back(st);
260 container[i].parent=container[i].child=-1;
261 container[i].degree=0;
262 container[i].in=true;
263 container[i].marked=false;
267 container[container[minimum].right_neighbor].left_neighbor=i;
268 container[i].right_neighbor=container[minimum].right_neighbor;
269 container[minimum].right_neighbor=i;
270 container[i].left_neighbor=minimum;
271 if ( comp( value, container[minimum].prio) ) minimum=i;
273 container[i].right_neighbor=container[i].left_neighbor=i;
276 container[i].prio=value;
280 template <typename Item, typename Prio, typename ItemIntMap,
282 void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
283 /*The first case is that there are only one root.*/
284 if ( container[minimum].left_neighbor==minimum ) {
285 container[minimum].in=false;
286 if ( container[minimum].degree!=0 ) {
287 makeroot(container[minimum].child);
288 minimum=container[minimum].child;
292 int right=container[minimum].right_neighbor;
294 container[minimum].in=false;
295 if ( container[minimum].degree > 0 ) {
296 int left=container[minimum].left_neighbor;
297 int child=container[minimum].child;
298 int last_child=container[child].left_neighbor;
302 container[left].right_neighbor=child;
303 container[child].left_neighbor=left;
304 container[right].left_neighbor=last_child;
305 container[last_child].right_neighbor=right;
309 } // the case where there are more roots
314 template <typename Item, typename Prio, typename ItemIntMap,
316 void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
320 if ( i >= 0 && container[i].in ) {
321 if ( container[i].parent!=-1 ) {
322 int p=container[i].parent;
326 minimum=i; //As if its prio would be -infinity
331 template <typename Item, typename Prio, typename ItemIntMap,
333 void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
334 (Item item, PrioType const value) {
336 container[i].prio=value;
337 int p=container[i].parent;
339 if ( p!=-1 && comp(value, container[p].prio) ) {
343 if ( comp(value, container[minimum].prio) ) minimum=i;
347 template <typename Item, typename Prio, typename ItemIntMap,
349 void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
351 int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
353 std::vector<int> A(maxdeg,-1);
356 *Recall that now minimum does not point to the minimum prio element.
357 *We set minimum to this during balance().
359 int anchor=container[minimum].left_neighbor;
365 if ( anchor==active ) end=true;
366 int d=container[active].degree;
367 next=container[active].right_neighbor;
370 if( comp(container[active].prio, container[A[d]].prio) ) {
383 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
387 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
388 s=container[s].right_neighbor;
392 template <typename Item, typename Prio, typename ItemIntMap,
394 void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
398 container[s].parent=-1;
399 s=container[s].right_neighbor;
404 template <typename Item, typename Prio, typename ItemIntMap,
406 void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
409 *Replacing a from the children of b.
411 --container[b].degree;
413 if ( container[b].degree !=0 ) {
414 int child=container[b].child;
416 container[b].child=container[child].right_neighbor;
421 /*Lacing a to the roots.*/
422 int right=container[minimum].right_neighbor;
423 container[minimum].right_neighbor=a;
424 container[a].left_neighbor=minimum;
425 container[a].right_neighbor=right;
426 container[right].left_neighbor=a;
428 container[a].parent=-1;
429 container[a].marked=false;
433 template <typename Item, typename Prio, typename ItemIntMap,
435 void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
438 if ( container[a].parent!=-1 ) {
439 int p=container[a].parent;
441 if ( container[a].marked==false ) container[a].marked=true;
450 template <typename Item, typename Prio, typename ItemIntMap,
452 void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
456 /*Lacing b under a.*/
457 container[b].parent=a;
459 if (container[a].degree==0) {
460 container[b].left_neighbor=b;
461 container[b].right_neighbor=b;
462 container[a].child=b;
464 int child=container[a].child;
465 int last_child=container[child].left_neighbor;
466 container[child].left_neighbor=b;
467 container[b].right_neighbor=child;
468 container[last_child].right_neighbor=b;
469 container[b].left_neighbor=last_child;
472 ++container[a].degree;
474 container[b].marked=false;
479 *It is invoked only if a has siblings.
481 template <typename Item, typename Prio, typename ItemIntMap,
483 void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
485 int leftn=container[a].left_neighbor;
486 int rightn=container[a].right_neighbor;
487 container[leftn].right_neighbor=rightn;
488 container[rightn].left_neighbor=leftn;
495 #endif //HUGO_FIB_HEAP_H