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 |
|
14 namespace hugo { |
|
15 |
|
16 /// \addtogroup auxdat |
|
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); |
|
211 void cascade(int a); |
|
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); |
|
328 cascade(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); |
|
345 cascade(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); |
|
448 cascade(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 |
|