39 ///efficient. \c Compare specifies the ordering of the priorities. In a heap |
39 ///efficient. \c Compare specifies the ordering of the priorities. In a heap |
40 ///one can change the priority of an item, add or erase an item, etc. |
40 ///one can change the priority of an item, add or erase an item, etc. |
41 /// |
41 /// |
42 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci |
42 ///The methods \ref increase and \ref erase are not efficient in a Fibonacci |
43 ///heap. In case of many calls to these operations, it is better to use a |
43 ///heap. In case of many calls to these operations, it is better to use a |
44 ///\e binary \e heap. |
44 ///\ref BinHeap "binary heap". |
45 /// |
45 /// |
46 ///\param Prio Type of the priority of the items. |
46 ///\param _Prio Type of the priority of the items. |
47 ///\param ItemIntMap A read and writable Item int map, used internally |
47 ///\param _ItemIntMap A read and writable Item int map, used internally |
48 ///to handle the cross references. |
48 ///to handle the cross references. |
49 ///\param Compare A class for the ordering of the priorities. The |
49 ///\param _Compare A class for the ordering of the priorities. The |
50 ///default is \c std::less<Prio>. |
50 ///default is \c std::less<_Prio>. |
51 /// |
51 /// |
52 ///\sa BinHeap |
52 ///\sa BinHeap |
53 ///\sa Dijkstra |
53 ///\sa Dijkstra |
54 ///\author Jacint Szabo |
54 ///\author Jacint Szabo |
55 |
55 |
56 #ifdef DOXYGEN |
56 #ifdef DOXYGEN |
57 template <typename Prio, |
57 template <typename _Prio, |
58 typename ItemIntMap, |
58 typename _ItemIntMap, |
59 typename Compare> |
59 typename _Compare> |
60 #else |
60 #else |
61 template <typename Prio, |
61 template <typename _Prio, |
62 typename ItemIntMap, |
62 typename _ItemIntMap, |
63 typename Compare = std::less<Prio> > |
63 typename _Compare = std::less<_Prio> > |
64 #endif |
64 #endif |
65 class FibHeap { |
65 class FibHeap { |
66 public: |
66 public: |
|
67 typedef _ItemIntMap ItemIntMap; |
|
68 typedef _Prio Prio; |
67 typedef typename ItemIntMap::Key Item; |
69 typedef typename ItemIntMap::Key Item; |
68 typedef Prio PrioType; |
70 typedef std::pair<Item,Prio> Pair; |
|
71 typedef _Compare Compare; |
69 |
72 |
70 private: |
73 private: |
71 class store; |
74 class store; |
72 |
75 |
73 std::vector<store> container; |
76 std::vector<store> container; |
126 /// if \c item was already there. |
129 /// if \c item was already there. |
127 /// |
130 /// |
128 /// This method calls \ref push(\c item, \c value) if \c item is not |
131 /// This method calls \ref push(\c item, \c value) if \c item is not |
129 /// stored in the heap and it calls \ref decrease(\c item, \c value) or |
132 /// stored in the heap and it calls \ref decrease(\c item, \c value) or |
130 /// \ref increase(\c item, \c value) otherwise. |
133 /// \ref increase(\c item, \c value) otherwise. |
131 void set (Item const item, PrioType const value); |
134 void set (const Item& item, const Prio& value) { |
|
135 int i=iimap[item]; |
|
136 if ( i >= 0 && container[i].in ) { |
|
137 if ( comp(value, container[i].prio) ) decrease(item, value); |
|
138 if ( comp(container[i].prio, value) ) increase(item, value); |
|
139 } else push(item, value); |
|
140 } |
132 |
141 |
133 /// \brief Adds \c item to the heap with priority \c value. |
142 /// \brief Adds \c item to the heap with priority \c value. |
134 /// |
143 /// |
135 /// Adds \c item to the heap with priority \c value. |
144 /// Adds \c item to the heap with priority \c value. |
136 /// \pre \c item must not be stored in the heap. |
145 /// \pre \c item must not be stored in the heap. |
137 void push (Item const item, PrioType const value); |
146 void push (const Item& item, const Prio& value) { |
138 |
|
139 /// \brief Returns the item with minimum priority relative to \c Compare. |
|
140 /// |
|
141 /// This method returns the item with minimum priority relative to \c |
|
142 /// Compare. |
|
143 /// \pre The heap must be nonempty. |
|
144 Item top() const { return container[minimum].name; } |
|
145 |
|
146 /// \brief Returns the minimum priority relative to \c Compare. |
|
147 /// |
|
148 /// It returns the minimum priority relative to \c Compare. |
|
149 /// \pre The heap must be nonempty. |
|
150 PrioType prio() const { return container[minimum].prio; } |
|
151 |
|
152 /// \brief Returns the priority of \c item. |
|
153 /// |
|
154 /// This function returns the priority of \c item. |
|
155 /// \pre \c item must be in the heap. |
|
156 PrioType& operator[](const Item& item) { |
|
157 return container[iimap[item]].prio; |
|
158 } |
|
159 |
|
160 /// \brief Returns the priority of \c item. |
|
161 /// |
|
162 /// It returns the priority of \c item. |
|
163 /// \pre \c item must be in the heap. |
|
164 const PrioType& operator[](const Item& item) const { |
|
165 return container[iimap[item]].prio; |
|
166 } |
|
167 |
|
168 |
|
169 /// \brief Deletes the item with minimum priority relative to \c Compare. |
|
170 /// |
|
171 /// This method deletes the item with minimum priority relative to \c |
|
172 /// Compare from the heap. |
|
173 /// \pre The heap must be non-empty. |
|
174 void pop(); |
|
175 |
|
176 /// \brief Deletes \c item from the heap. |
|
177 /// |
|
178 /// This method deletes \c item from the heap, if \c item was already |
|
179 /// stored in the heap. It is quite inefficient in Fibonacci heaps. |
|
180 void erase (const Item& item); |
|
181 |
|
182 /// \brief Decreases the priority of \c item to \c value. |
|
183 /// |
|
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. |
|
187 void decrease (Item item, PrioType const value); |
|
188 |
|
189 /// \brief Increases the priority of \c item to \c value. |
|
190 /// |
|
191 /// This method sets the priority of \c item to \c value. Though |
|
192 /// there is no precondition on the priority of \c item, this |
|
193 /// method should be used only if it is indeed necessary to increase |
|
194 /// (relative to \c Compare) the priority of \c item, because this |
|
195 /// method is inefficient. |
|
196 void increase (Item item, PrioType const value) { |
|
197 erase(item); |
|
198 push(item, value); |
|
199 } |
|
200 |
|
201 |
|
202 /// \brief Returns if \c item is in, has already been in, or has never |
|
203 /// been in the heap. |
|
204 /// |
|
205 /// This method returns PRE_HEAP if \c item has never been in the |
|
206 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
|
207 /// otherwise. In the latter case it is possible that \c item will |
|
208 /// get back to the heap again. |
|
209 state_enum state(const Item &item) const { |
|
210 int i=iimap[item]; |
|
211 if( i>=0 ) { |
|
212 if ( container[i].in ) i=0; |
|
213 else i=-2; |
|
214 } |
|
215 return state_enum(i); |
|
216 } |
|
217 |
|
218 /// \brief Sets the state of the \c item in the heap. |
|
219 /// |
|
220 /// Sets the state of the \c item in the heap. It can be used to |
|
221 /// manually clear the heap when it is important to achive the |
|
222 /// better time complexity. |
|
223 /// \param i The item. |
|
224 /// \param st The state. It should not be \c IN_HEAP. |
|
225 void state(const Item& i, state_enum st) { |
|
226 switch (st) { |
|
227 case POST_HEAP: |
|
228 case PRE_HEAP: |
|
229 if (state(i) == IN_HEAP) { |
|
230 erase(i); |
|
231 } |
|
232 iimap[i] = st; |
|
233 break; |
|
234 case IN_HEAP: |
|
235 break; |
|
236 } |
|
237 } |
|
238 |
|
239 private: |
|
240 |
|
241 void balance(); |
|
242 void makeroot(int c); |
|
243 void cut(int a, int b); |
|
244 void cascade(int a); |
|
245 void fuse(int a, int b); |
|
246 void unlace(int a); |
|
247 |
|
248 |
|
249 class store { |
|
250 friend class FibHeap; |
|
251 |
|
252 Item name; |
|
253 int parent; |
|
254 int left_neighbor; |
|
255 int right_neighbor; |
|
256 int child; |
|
257 int degree; |
|
258 bool marked; |
|
259 bool in; |
|
260 PrioType prio; |
|
261 |
|
262 store() : parent(-1), child(-1), degree(), marked(false), in(true) {} |
|
263 }; |
|
264 }; |
|
265 |
|
266 |
|
267 |
|
268 // ********************************************************************** |
|
269 // IMPLEMENTATIONS |
|
270 // ********************************************************************** |
|
271 |
|
272 template <typename Prio, typename ItemIntMap, |
|
273 typename Compare> |
|
274 void FibHeap<Prio, ItemIntMap, Compare>::set |
|
275 (Item const item, PrioType const value) |
|
276 { |
|
277 int i=iimap[item]; |
|
278 if ( i >= 0 && container[i].in ) { |
|
279 if ( comp(value, container[i].prio) ) decrease(item, value); |
|
280 if ( comp(container[i].prio, value) ) increase(item, value); |
|
281 } else push(item, value); |
|
282 } |
|
283 |
|
284 template <typename Prio, typename ItemIntMap, |
|
285 typename Compare> |
|
286 void FibHeap<Prio, ItemIntMap, Compare>::push |
|
287 (Item const item, PrioType const value) { |
|
288 int i=iimap[item]; |
147 int i=iimap[item]; |
289 if ( i < 0 ) { |
148 if ( i < 0 ) { |
290 int s=container.size(); |
149 int s=container.size(); |
291 iimap.set( item, s ); |
150 iimap.set( item, s ); |
292 store st; |
151 store st; |
312 } |
171 } |
313 container[i].prio=value; |
172 container[i].prio=value; |
314 ++num_items; |
173 ++num_items; |
315 } |
174 } |
316 |
175 |
317 template <typename Prio, typename ItemIntMap, |
176 /// \brief Returns the item with minimum priority relative to \c Compare. |
318 typename Compare> |
177 /// |
319 void FibHeap<Prio, ItemIntMap, Compare>::pop() { |
178 /// This method returns the item with minimum priority relative to \c |
|
179 /// Compare. |
|
180 /// \pre The heap must be nonempty. |
|
181 Item top() const { return container[minimum].name; } |
|
182 |
|
183 /// \brief Returns the minimum priority relative to \c Compare. |
|
184 /// |
|
185 /// It returns the minimum priority relative to \c Compare. |
|
186 /// \pre The heap must be nonempty. |
|
187 const Prio& prio() const { return container[minimum].prio; } |
|
188 |
|
189 /// \brief Returns the priority of \c item. |
|
190 /// |
|
191 /// It returns the priority of \c item. |
|
192 /// \pre \c item must be in the heap. |
|
193 const Prio& operator[](const Item& item) const { |
|
194 return container[iimap[item]].prio; |
|
195 } |
|
196 |
|
197 /// \brief Deletes the item with minimum priority relative to \c Compare. |
|
198 /// |
|
199 /// This method deletes the item with minimum priority relative to \c |
|
200 /// Compare from the heap. |
|
201 /// \pre The heap must be non-empty. |
|
202 void pop() { |
320 /*The first case is that there are only one root.*/ |
203 /*The first case is that there are only one root.*/ |
321 if ( container[minimum].left_neighbor==minimum ) { |
204 if ( container[minimum].left_neighbor==minimum ) { |
322 container[minimum].in=false; |
205 container[minimum].in=false; |
323 if ( container[minimum].degree!=0 ) { |
206 if ( container[minimum].degree!=0 ) { |
324 makeroot(container[minimum].child); |
207 makeroot(container[minimum].child); |
361 cascade(p); |
244 cascade(p); |
362 } |
245 } |
363 minimum=i; //As if its prio would be -infinity |
246 minimum=i; //As if its prio would be -infinity |
364 pop(); |
247 pop(); |
365 } |
248 } |
366 } |
249 } |
367 |
250 |
368 template <typename Prio, typename ItemIntMap, |
251 /// \brief Decreases the priority of \c item to \c value. |
369 typename Compare> |
252 /// |
370 void FibHeap<Prio, ItemIntMap, Compare>::decrease |
253 /// This method decreases the priority of \c item to \c value. |
371 (Item item, PrioType const value) { |
254 /// \pre \c item must be stored in the heap with priority at least \c |
|
255 /// value relative to \c Compare. |
|
256 void decrease (Item item, const Prio& value) { |
372 int i=iimap[item]; |
257 int i=iimap[item]; |
373 container[i].prio=value; |
258 container[i].prio=value; |
374 int p=container[i].parent; |
259 int p=container[i].parent; |
375 |
260 |
376 if ( p!=-1 && comp(value, container[p].prio) ) { |
261 if ( p!=-1 && comp(value, container[p].prio) ) { |
377 cut(i,p); |
262 cut(i,p); |
378 cascade(p); |
263 cascade(p); |
379 } |
264 } |
380 if ( comp(value, container[minimum].prio) ) minimum=i; |
265 if ( comp(value, container[minimum].prio) ) minimum=i; |
381 } |
266 } |
382 |
267 |
383 |
268 /// \brief Increases the priority of \c item to \c value. |
384 template <typename Prio, typename ItemIntMap, |
269 /// |
385 typename Compare> |
270 /// This method sets the priority of \c item to \c value. Though |
386 void FibHeap<Prio, ItemIntMap, Compare>::balance() { |
271 /// there is no precondition on the priority of \c item, this |
387 |
272 /// method should be used only if it is indeed necessary to increase |
388 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; |
273 /// (relative to \c Compare) the priority of \c item, because this |
|
274 /// method is inefficient. |
|
275 void increase (Item item, const Prio& value) { |
|
276 erase(item); |
|
277 push(item, value); |
|
278 } |
|
279 |
|
280 |
|
281 /// \brief Returns if \c item is in, has already been in, or has never |
|
282 /// been in the heap. |
|
283 /// |
|
284 /// This method returns PRE_HEAP if \c item has never been in the |
|
285 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
|
286 /// otherwise. In the latter case it is possible that \c item will |
|
287 /// get back to the heap again. |
|
288 State state(const Item &item) const { |
|
289 int i=iimap[item]; |
|
290 if( i>=0 ) { |
|
291 if ( container[i].in ) i=0; |
|
292 else i=-2; |
|
293 } |
|
294 return State(i); |
|
295 } |
|
296 |
|
297 /// \brief Sets the state of the \c item in the heap. |
|
298 /// |
|
299 /// Sets the state of the \c item in the heap. It can be used to |
|
300 /// manually clear the heap when it is important to achive the |
|
301 /// better time complexity. |
|
302 /// \param i The item. |
|
303 /// \param st The state. It should not be \c IN_HEAP. |
|
304 void state(const Item& i, State st) { |
|
305 switch (st) { |
|
306 case POST_HEAP: |
|
307 case PRE_HEAP: |
|
308 if (state(i) == IN_HEAP) { |
|
309 erase(i); |
|
310 } |
|
311 iimap[i] = st; |
|
312 break; |
|
313 case IN_HEAP: |
|
314 break; |
|
315 } |
|
316 } |
|
317 |
|
318 private: |
|
319 |
|
320 void balance() { |
|
321 |
|
322 int maxdeg=int( std::floor( 2.08*log(double(container.size()))))+1; |
389 |
323 |
390 std::vector<int> A(maxdeg,-1); |
324 std::vector<int> A(maxdeg,-1); |
391 |
325 |
392 /* |
326 /* |
393 *Recall that now minimum does not point to the minimum prio element. |
327 *Recall that now minimum does not point to the minimum prio element. |
394 *We set minimum to this during balance(). |
328 *We set minimum to this during balance(). |
395 */ |
329 */ |
396 int anchor=container[minimum].left_neighbor; |
330 int anchor=container[minimum].left_neighbor; |
397 int next=minimum; |
331 int next=minimum; |
398 bool end=false; |
332 bool end=false; |
399 |
333 |
400 do { |
334 do { |
401 int active=next; |
335 int active=next; |
402 if ( anchor==active ) end=true; |
336 if ( anchor==active ) end=true; |
403 int d=container[active].degree; |
337 int d=container[active].degree; |
404 next=container[active].right_neighbor; |
338 next=container[active].right_neighbor; |
405 |
339 |
412 } |
346 } |
413 A[d]=-1; |
347 A[d]=-1; |
414 ++d; |
348 ++d; |
415 } |
349 } |
416 A[d]=active; |
350 A[d]=active; |
417 } while ( !end ); |
351 } while ( !end ); |
418 |
352 |
419 |
353 |
420 while ( container[minimum].parent >=0 ) minimum=container[minimum].parent; |
354 while ( container[minimum].parent >=0 ) |
421 int s=minimum; |
355 minimum=container[minimum].parent; |
422 int m=minimum; |
356 int s=minimum; |
423 do { |
357 int m=minimum; |
424 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; |
358 do { |
425 s=container[s].right_neighbor; |
359 if ( comp(container[s].prio, container[minimum].prio) ) minimum=s; |
426 } while ( s != m ); |
360 s=container[s].right_neighbor; |
427 } |
361 } while ( s != m ); |
428 |
362 } |
429 template <typename Prio, typename ItemIntMap, |
363 |
430 typename Compare> |
364 void makeroot(int c) { |
431 void FibHeap<Prio, ItemIntMap, Compare>::makeroot |
|
432 (int c) { |
|
433 int s=c; |
365 int s=c; |
434 do { |
366 do { |
435 container[s].parent=-1; |
367 container[s].parent=-1; |
436 s=container[s].right_neighbor; |
368 s=container[s].right_neighbor; |
437 } while ( s != c ); |
369 } while ( s != c ); |
438 } |
370 } |
439 |
371 |
440 |
372 void cut(int a, int b) { |
441 template <typename Prio, typename ItemIntMap, |
373 /* |
442 typename Compare> |
374 *Replacing a from the children of b. |
443 void FibHeap<Prio, ItemIntMap, Compare>::cut |
375 */ |
444 (int a, int b) { |
376 --container[b].degree; |
445 /* |
377 |
446 *Replacing a from the children of b. |
378 if ( container[b].degree !=0 ) { |
447 */ |
379 int child=container[b].child; |
448 --container[b].degree; |
380 if ( child==a ) |
449 |
381 container[b].child=container[child].right_neighbor; |
450 if ( container[b].degree !=0 ) { |
382 unlace(a); |
451 int child=container[b].child; |
383 } |
452 if ( child==a ) |
384 |
453 container[b].child=container[child].right_neighbor; |
385 |
454 unlace(a); |
386 /*Lacing a to the roots.*/ |
455 } |
387 int right=container[minimum].right_neighbor; |
456 |
388 container[minimum].right_neighbor=a; |
457 |
389 container[a].left_neighbor=minimum; |
458 /*Lacing a to the roots.*/ |
390 container[a].right_neighbor=right; |
459 int right=container[minimum].right_neighbor; |
391 container[right].left_neighbor=a; |
460 container[minimum].right_neighbor=a; |
392 |
461 container[a].left_neighbor=minimum; |
393 container[a].parent=-1; |
462 container[a].right_neighbor=right; |
394 container[a].marked=false; |
463 container[right].left_neighbor=a; |
395 } |
464 |
396 |
465 container[a].parent=-1; |
397 void cascade(int a) { |
466 container[a].marked=false; |
|
467 } |
|
468 |
|
469 |
|
470 template <typename Prio, typename ItemIntMap, |
|
471 typename Compare> |
|
472 void FibHeap<Prio, ItemIntMap, Compare>::cascade |
|
473 (int a) |
|
474 { |
|
475 if ( container[a].parent!=-1 ) { |
398 if ( container[a].parent!=-1 ) { |
476 int p=container[a].parent; |
399 int p=container[a].parent; |
477 |
400 |
478 if ( container[a].marked==false ) container[a].marked=true; |
401 if ( container[a].marked==false ) container[a].marked=true; |
479 else { |
402 else { |