Another bugfix.
2 * lemon/fib_heap.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, 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, used internally
48 ///to handle the cross references.
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
94 \c _iimap should be given to the constructor, since it is
95 used internally to handle the cross references.
97 explicit FibHeap(ItemIntMap &_iimap)
98 : minimum(0), iimap(_iimap), num_items() {}
103 \c _iimap should be given to the constructor, since it is used
104 internally to handle the cross references. \c _comp is an
105 object for ordering of the priorities.
107 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(0),
108 iimap(_iimap), comp(_comp), num_items() {}
110 ///The number of items stored in the heap.
113 Returns the number of items stored in the heap.
115 int size() const { return num_items; }
117 ///Checks if the heap stores no items.
120 Returns \c true if and only if the heap stores no items.
122 bool empty() const { return num_items==0; }
124 ///\c item gets to the heap with priority \c value independently if \c item was already there.
127 This method calls \ref push(\c item, \c value) if \c item is not
128 stored in the heap and it calls \ref decrease(\c item, \c value) or
129 \ref increase(\c item, \c value) otherwise.
131 void set (Item const item, PrioType const value);
133 ///Adds \c item to the heap with priority \c value.
136 Adds \c item to the heap with priority \c value.
137 \pre \c item must not be stored in the heap.
139 void push (Item const item, PrioType const value);
141 ///Returns the item with minimum priority relative to \c Compare.
144 This method returns the item with minimum priority relative to \c
146 \pre The heap must be nonempty.
148 Item top() const { return container[minimum].name; }
150 ///Returns the minimum priority relative to \c Compare.
153 It returns the minimum priority relative to \c Compare.
154 \pre The heap must be nonempty.
156 PrioType prio() const { return container[minimum].prio; }
158 ///Returns the priority of \c item.
161 This function returns the priority of \c item.
162 \pre \c item must be in the heap.
164 PrioType& operator[](const Item& item) {
165 return container[iimap[item]].prio;
168 ///Returns the priority of \c item.
171 It returns the priority of \c item.
172 \pre \c item must be in the heap.
174 const PrioType& operator[](const Item& item) const {
175 return container[iimap[item]].prio;
179 ///Deletes the item with minimum priority relative to \c Compare.
182 This method deletes the item with minimum priority relative to \c
183 Compare from the heap.
184 \pre The heap must be non-empty.
188 ///Deletes \c item from the heap.
191 This method deletes \c item from the heap, if \c item was already
192 stored in the heap. It is quite inefficient in Fibonacci heaps.
194 void erase (const Item& item);
196 ///Decreases the priority of \c item to \c value.
199 This method decreases the priority of \c item to \c value.
200 \pre \c item must be stored in the heap with priority at least \c
201 value relative to \c Compare.
203 void decrease (Item item, PrioType const value);
205 ///Increases the priority of \c item to \c value.
208 This method sets the priority of \c item to \c value. Though
209 there is no precondition on the priority of \c item, this
210 method should be used only if it is indeed necessary to increase
211 (relative to \c Compare) the priority of \c item, because this
212 method is inefficient.
214 void increase (Item item, PrioType const value) {
220 ///Returns if \c item is in, has already been in, or has never been in the heap.
223 This method returns PRE_HEAP if \c item has never been in the
224 heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
225 otherwise. In the latter case it is possible that \c item will
226 get back to the heap again.
228 state_enum state(const Item &item) const {
231 if ( container[i].in ) i=0;
234 return state_enum(i);
240 void makeroot(int c);
241 void cut(int a, int b);
243 void fuse(int a, int b);
248 friend class FibHeap;
260 store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
266 // **********************************************************************
268 // **********************************************************************
270 template <typename Item, typename Prio, typename ItemIntMap,
272 void FibHeap<Item, Prio, ItemIntMap, Compare>::set
273 (Item const item, PrioType const value)
276 if ( i >= 0 && container[i].in ) {
277 if ( comp(value, container[i].prio) ) decrease(item, value);
278 if ( comp(container[i].prio, value) ) increase(item, value);
279 } else push(item, value);
282 template <typename Item, typename Prio, typename ItemIntMap,
284 void FibHeap<Item, Prio, ItemIntMap, Compare>::push
285 (Item const item, PrioType const value) {
288 int s=container.size();
289 iimap.set( item, s );
292 container.push_back(st);
295 container[i].parent=container[i].child=-1;
296 container[i].degree=0;
297 container[i].in=true;
298 container[i].marked=false;
302 container[container[minimum].right_neighbor].left_neighbor=i;
303 container[i].right_neighbor=container[minimum].right_neighbor;
304 container[minimum].right_neighbor=i;
305 container[i].left_neighbor=minimum;
306 if ( comp( value, container[minimum].prio) ) minimum=i;
308 container[i].right_neighbor=container[i].left_neighbor=i;
311 container[i].prio=value;
315 template <typename Item, typename Prio, typename ItemIntMap,
317 void FibHeap<Item, Prio, ItemIntMap, Compare>::pop() {
318 /*The first case is that there are only one root.*/
319 if ( container[minimum].left_neighbor==minimum ) {
320 container[minimum].in=false;
321 if ( container[minimum].degree!=0 ) {
322 makeroot(container[minimum].child);
323 minimum=container[minimum].child;
327 int right=container[minimum].right_neighbor;
329 container[minimum].in=false;
330 if ( container[minimum].degree > 0 ) {
331 int left=container[minimum].left_neighbor;
332 int child=container[minimum].child;
333 int last_child=container[child].left_neighbor;
337 container[left].right_neighbor=child;
338 container[child].left_neighbor=left;
339 container[right].left_neighbor=last_child;
340 container[last_child].right_neighbor=right;
344 } // the case where there are more roots
349 template <typename Item, typename Prio, typename ItemIntMap,
351 void FibHeap<Item, Prio, ItemIntMap, Compare>::erase
355 if ( i >= 0 && container[i].in ) {
356 if ( container[i].parent!=-1 ) {
357 int p=container[i].parent;
361 minimum=i; //As if its prio would be -infinity
366 template <typename Item, typename Prio, typename ItemIntMap,
368 void FibHeap<Item, Prio, ItemIntMap, Compare>::decrease
369 (Item item, PrioType const value) {
371 container[i].prio=value;
372 int p=container[i].parent;
374 if ( p!=-1 && comp(value, container[p].prio) ) {
378 if ( comp(value, container[minimum].prio) ) minimum=i;
382 template <typename Item, typename Prio, typename ItemIntMap,
384 void FibHeap<Item, Prio, ItemIntMap, Compare>::balance() {
386 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1;
388 std::vector<int> A(maxdeg,-1);
391 *Recall that now minimum does not point to the minimum prio element.
392 *We set minimum to this during balance().
394 int anchor=container[minimum].left_neighbor;
400 if ( anchor==active ) end=true;
401 int d=container[active].degree;
402 next=container[active].right_neighbor;
405 if( comp(container[active].prio, container[A[d]].prio) ) {
418 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent;
422 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s;
423 s=container[s].right_neighbor;
427 template <typename Item, typename Prio, typename ItemIntMap,
429 void FibHeap<Item, Prio, ItemIntMap, Compare>::makeroot
433 container[s].parent=-1;
434 s=container[s].right_neighbor;
439 template <typename Item, typename Prio, typename ItemIntMap,
441 void FibHeap<Item, Prio, ItemIntMap, Compare>::cut
444 *Replacing a from the children of b.
446 --container[b].degree;
448 if ( container[b].degree !=0 ) {
449 int child=container[b].child;
451 container[b].child=container[child].right_neighbor;
456 /*Lacing a to the roots.*/
457 int right=container[minimum].right_neighbor;
458 container[minimum].right_neighbor=a;
459 container[a].left_neighbor=minimum;
460 container[a].right_neighbor=right;
461 container[right].left_neighbor=a;
463 container[a].parent=-1;
464 container[a].marked=false;
468 template <typename Item, typename Prio, typename ItemIntMap,
470 void FibHeap<Item, Prio, ItemIntMap, Compare>::cascade
473 if ( container[a].parent!=-1 ) {
474 int p=container[a].parent;
476 if ( container[a].marked==false ) container[a].marked=true;
485 template <typename Item, typename Prio, typename ItemIntMap,
487 void FibHeap<Item, Prio, ItemIntMap, Compare>::fuse
491 /*Lacing b under a.*/
492 container[b].parent=a;
494 if (container[a].degree==0) {
495 container[b].left_neighbor=b;
496 container[b].right_neighbor=b;
497 container[a].child=b;
499 int child=container[a].child;
500 int last_child=container[child].left_neighbor;
501 container[child].left_neighbor=b;
502 container[b].right_neighbor=child;
503 container[last_child].right_neighbor=b;
504 container[b].left_neighbor=last_child;
507 ++container[a].degree;
509 container[b].marked=false;
514 *It is invoked only if a has siblings.
516 template <typename Item, typename Prio, typename ItemIntMap,
518 void FibHeap<Item, Prio, ItemIntMap, Compare>::unlace
520 int leftn=container[a].left_neighbor;
521 int rightn=container[a].right_neighbor;
522 container[leftn].right_neighbor=rightn;
523 container[rightn].left_neighbor=leftn;
530 #endif //LEMON_FIB_HEAP_H