graphwrapper dox. everybody is asked to read doxygen.log
2 * src/lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
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.
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
17 #ifndef LEMON_FIB_HEAP_H
18 #define LEMON_FIB_HEAP_H
22 ///\brief Fibonacci Heap implementation.
30 /// \addtogroup auxdat
35 ///This class implements the \e Fibonacci \e heap data structure. A \e heap
36 ///is a data structure for storing items with specified values called \e
37 ///priorities in such a way that finding the item with minimum priority is
38 ///efficient. \c Compare specifies the ordering of the priorities. In a heap
39 ///one can change the priority of an item, add or erase an item, etc.
41 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci
42 ///heap. In case of many calls to these operations, it is better to use a
45 ///\param Item Type of the items to be stored.
46 ///\param Prio Type of the priority of the items.
47 ///\param ItemIntMap A read and writable Item int map, for the usage of
49 ///\param Compare A class for the ordering of the priorities. The
50 ///default is \c std::less<Prio>.
54 ///\author Jacint Szabo
57 template <typename Item,
62 template <typename Item,
65 typename Compare = std::less<Prio> >
69 typedef Prio PrioType;
74 std::vector<store> container;
81 ///Status of the nodes
83 ///The node is in the heap
85 ///The node has never been in the heap
87 ///The node was in the heap but it got out of it
91 FibHeap(ItemIntMap &_iimap) : minimum(0), iimap(_iimap), num_items() {}
92 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
93 iimap(_iimap), comp(_comp), num_items() {}
95 ///The number of items stored in the heap.
98 Returns the number of items stored in the heap.
100 int size() const { return num_items; }
102 ///Checks if the heap stores no items.
105 Returns \c true if and only if the heap stores no items.
107 bool empty() const { return num_items==0; }
109 ///\c item gets to the heap with priority \c value independently if \c item was already there.
112 This method calls \ref push(\c item, \c value) if \c item is not
113 stored in the heap and it calls \ref decrease(\c item, \c value) or
114 \ref increase(\c item, \c value) otherwise.
116 void set (Item const item, PrioType const value);
118 ///Adds \c item to the heap with priority \c value.
121 Adds \c item to the heap with priority \c value.
122 \pre \c item must not be stored in the heap.
124 void push (Item const item, PrioType const value);
126 ///Returns the item with minimum priority relative to \c Compare.
129 This method returns the item with minimum priority relative to \c
131 \pre The heap must be nonempty.
133 Item top() const { return container[minimum].name; }
135 ///Returns the minimum priority relative to \c Compare.
138 It returns the minimum priority relative to \c Compare.
139 \pre The heap must be nonempty.
141 PrioType prio() const { return container[minimum].prio; }
143 ///Returns the priority of \c item.
146 This function returns the priority of \c item.
147 \pre \c item must be in the heap.
149 PrioType& operator[](const Item& item) {
150 return container[iimap[item]].prio;
153 ///Returns the priority of \c item.
156 It returns the priority of \c item.
157 \pre \c item must be in the heap.
159 const PrioType& operator[](const Item& item) const {
160 return container[iimap[item]].prio;
164 ///Deletes the item with minimum priority relative to \c Compare.
167 This method deletes the item with minimum priority relative to \c
168 Compare from the heap.
169 \pre The heap must be non-empty.
173 ///Deletes \c item from the heap.
176 This method deletes \c item from the heap, if \c item was already
177 stored in the heap. It is quite inefficient in Fibonacci heaps.
179 void erase (const Item& item);
181 ///Decreases the priority of \c item to \c value.
184 This method decreases the priority of \c item to \c value.
185 \pre \c item must be stored in the heap with priority at least \c
186 value relative to \c Compare.
188 void decrease (Item item, PrioType const value);
190 ///Increases the priority of \c item to \c value.
193 This method sets the priority of \c item to \c value. Though
194 there is no precondition on the priority of \c item, this
195 method should be used only if it is indeed necessary to increase
196 (relative to \c Compare) the priority of \c item, because this
197 method is inefficient.
199 void increase (Item item, PrioType const value) {
205 ///Returns if \c item is in, has already been in, or has never been in the heap.
208 This method returns PRE_HEAP if \c item has never been in the
209 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
210 otherwise. In the latter case it is possible that \c item will
211 get back to the heap again.
213 state_enum state(const Item &item) const {
216 if ( container[i].in ) i=0;
219 return state_enum(i);
225 void makeroot(int c);
226 void cut(int a, int b);
228 void fuse(int a, int b);
233 friend class FibHeap;
245 store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
251 // **********************************************************************
253 // **********************************************************************
255 template <typename Item, typename Prio, typename ItemIntMap,
257 void FibHeap<Item, Prio, ItemIntMap, Compare>::set
258 (Item const item, PrioType const value)
261 if ( i >= 0 && container[i].in ) {
262 if ( comp(value, container[i].prio) ) decrease(item, value);
263 if ( comp(container[i].prio, value) ) increase(item, value);
264 } else push(item, value);
267 template <typename Item, typename Prio, typename ItemIntMap,
269 void FibHeap<Item, Prio, ItemIntMap, Compare>::push
270 (Item const item, PrioType const value) {
273 int s=container.size();
274 iimap.set( item, s );
277 container.push_back(st);
280 container[i].parent=container[i].child=-1;
281 container[i].degree=0;
282 container[i].in=true;
283 container[i].marked=false;
287 container[container[minimum].right_neighbor].left_neighbor=i;
288 container[i].right_neighbor=container[minimum].right_neighbor;
289 container[minimum].right_neighbor=i;
290 container[i].left_neighbor=minimum;
291 if ( comp( value, container[minimum].prio) ) minimum=i;
293 container[i].right_neighbor=container[i].left_neighbor=i;
296 container[i].prio=value;
300 template <typename Item, typename Prio, typename ItemIntMap,
302 void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
303 /*The first case is that there are only one root.*/
304 if ( container[minimum].left_neighbor==minimum ) {
305 container[minimum].in=false;
306 if ( container[minimum].degree!=0 ) {
307 makeroot(container[minimum].child);
308 minimum=container[minimum].child;
312 int right=container[minimum].right_neighbor;
314 container[minimum].in=false;
315 if ( container[minimum].degree > 0 ) {
316 int left=container[minimum].left_neighbor;
317 int child=container[minimum].child;
318 int last_child=container[child].left_neighbor;
322 container[left].right_neighbor=child;
323 container[child].left_neighbor=left;
324 container[right].left_neighbor=last_child;
325 container[last_child].right_neighbor=right;
329 } // the case where there are more roots
334 template <typename Item, typename Prio, typename ItemIntMap,
336 void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
340 if ( i >= 0 && container[i].in ) {
341 if ( container[i].parent!=-1 ) {
342 int p=container[i].parent;
346 minimum=i; //As if its prio would be -infinity
351 template <typename Item, typename Prio, typename ItemIntMap,
353 void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
354 (Item item, PrioType const value) {
356 container[i].prio=value;
357 int p=container[i].parent;
359 if ( p!=-1 && comp(value, container[p].prio) ) {
363 if ( comp(value, container[minimum].prio) ) minimum=i;
367 template <typename Item, typename Prio, typename ItemIntMap,
369 void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
371 int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
373 std::vector<int> A(maxdeg,-1);
376 *Recall that now minimum does not point to the minimum prio element.
377 *We set minimum to this during balance().
379 int anchor=container[minimum].left_neighbor;
385 if ( anchor==active ) end=true;
386 int d=container[active].degree;
387 next=container[active].right_neighbor;
390 if( comp(container[active].prio, container[A[d]].prio) ) {
403 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
407 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
408 s=container[s].right_neighbor;
412 template <typename Item, typename Prio, typename ItemIntMap,
414 void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
418 container[s].parent=-1;
419 s=container[s].right_neighbor;
424 template <typename Item, typename Prio, typename ItemIntMap,
426 void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
429 *Replacing a from the children of b.
431 --container[b].degree;
433 if ( container[b].degree !=0 ) {
434 int child=container[b].child;
436 container[b].child=container[child].right_neighbor;
441 /*Lacing a to the roots.*/
442 int right=container[minimum].right_neighbor;
443 container[minimum].right_neighbor=a;
444 container[a].left_neighbor=minimum;
445 container[a].right_neighbor=right;
446 container[right].left_neighbor=a;
448 container[a].parent=-1;
449 container[a].marked=false;
453 template <typename Item, typename Prio, typename ItemIntMap,
455 void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
458 if ( container[a].parent!=-1 ) {
459 int p=container[a].parent;
461 if ( container[a].marked==false ) container[a].marked=true;
470 template <typename Item, typename Prio, typename ItemIntMap,
472 void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
476 /*Lacing b under a.*/
477 container[b].parent=a;
479 if (container[a].degree==0) {
480 container[b].left_neighbor=b;
481 container[b].right_neighbor=b;
482 container[a].child=b;
484 int child=container[a].child;
485 int last_child=container[child].left_neighbor;
486 container[child].left_neighbor=b;
487 container[b].right_neighbor=child;
488 container[last_child].right_neighbor=b;
489 container[b].left_neighbor=last_child;
492 ++container[a].degree;
494 container[b].marked=false;
499 *It is invoked only if a has siblings.
501 template <typename Item, typename Prio, typename ItemIntMap,
503 void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
505 int leftn=container[a].left_neighbor;
506 int rightn=container[a].right_neighbor;
507 container[leftn].right_neighbor=rightn;
508 container[rightn].left_neighbor=leftn;
515 #endif //LEMON_FIB_HEAP_H