|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #ifndef LEMON_BINOM_HEAP_H |
|
20 #define LEMON_BINOM_HEAP_H |
|
21 |
|
22 ///\file |
|
23 ///\ingroup auxdat |
|
24 ///\brief Binomial Heap implementation. |
|
25 |
|
26 #include <vector> |
|
27 #include <functional> |
|
28 #include <lemon/math.h> |
|
29 #include <lemon/counter.h> |
|
30 |
|
31 namespace lemon { |
|
32 |
|
33 /// \ingroup auxdat |
|
34 /// |
|
35 ///\brief Binomial Heap. |
|
36 /// |
|
37 ///This class implements the \e Binomial \e heap data structure. A \e heap |
|
38 ///is a data structure for storing items with specified values called \e |
|
39 ///priorities in such a way that finding the item with minimum priority is |
|
40 ///efficient. \c Compare specifies the ordering of the priorities. In a heap |
|
41 ///one can change the priority of an item, add or erase an item, etc. |
|
42 /// |
|
43 ///The methods \ref increase and \ref erase are not efficient in a Binomial |
|
44 ///heap. In case of many calls to these operations, it is better to use a |
|
45 ///\ref BinHeap "binary heap". |
|
46 /// |
|
47 ///\param _Prio Type of the priority of the items. |
|
48 ///\param _ItemIntMap A read and writable Item int map, used internally |
|
49 ///to handle the cross references. |
|
50 ///\param _Compare A class for the ordering of the priorities. The |
|
51 ///default is \c std::less<_Prio>. |
|
52 /// |
|
53 ///\sa BinHeap |
|
54 ///\sa Dijkstra |
|
55 ///\author Dorian Batha |
|
56 |
|
57 #ifdef DOXYGEN |
|
58 template <typename _Prio, |
|
59 typename _ItemIntMap, |
|
60 typename _Compare> |
|
61 #else |
|
62 template <typename _Prio, |
|
63 typename _ItemIntMap, |
|
64 typename _Compare = std::less<_Prio> > |
|
65 #endif |
|
66 class BinomHeap { |
|
67 public: |
|
68 typedef _ItemIntMap ItemIntMap; |
|
69 typedef _Prio Prio; |
|
70 typedef typename ItemIntMap::Key Item; |
|
71 typedef std::pair<Item,Prio> Pair; |
|
72 typedef _Compare Compare; |
|
73 |
|
74 private: |
|
75 class store; |
|
76 |
|
77 std::vector<store> container; |
|
78 int minimum, head; |
|
79 ItemIntMap &iimap; |
|
80 Compare comp; |
|
81 int num_items; |
|
82 |
|
83 public: |
|
84 ///Status of the nodes |
|
85 enum State { |
|
86 ///The node is in the heap |
|
87 IN_HEAP = 0, |
|
88 ///The node has never been in the heap |
|
89 PRE_HEAP = -1, |
|
90 ///The node was in the heap but it got out of it |
|
91 POST_HEAP = -2 |
|
92 }; |
|
93 |
|
94 /// \brief The constructor |
|
95 /// |
|
96 /// \c _iimap should be given to the constructor, since it is |
|
97 /// used internally to handle the cross references. |
|
98 explicit BinomHeap(ItemIntMap &_iimap) |
|
99 : minimum(0), head(-1), iimap(_iimap), num_items() {} |
|
100 |
|
101 /// \brief The constructor |
|
102 /// |
|
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. |
|
106 BinomHeap(ItemIntMap &_iimap, const Compare &_comp) |
|
107 : minimum(0), head(-1), iimap(_iimap), comp(_comp), num_items() {} |
|
108 |
|
109 /// \brief The number of items stored in the heap. |
|
110 /// |
|
111 /// Returns the number of items stored in the heap. |
|
112 int size() const { return num_items; } |
|
113 |
|
114 /// \brief Checks if the heap stores no items. |
|
115 /// |
|
116 /// Returns \c true if and only if the heap stores no items. |
|
117 bool empty() const { return num_items==0; } |
|
118 |
|
119 /// \brief Make empty this heap. |
|
120 /// |
|
121 /// Make empty this heap. It does not change the cross reference |
|
122 /// map. If you want to reuse a heap what is not surely empty you |
|
123 /// should first clear the heap and after that you should set the |
|
124 /// cross reference map for each item to \c PRE_HEAP. |
|
125 void clear() { |
|
126 container.clear(); minimum=0; num_items=0; head=-1; |
|
127 } |
|
128 |
|
129 /// \brief \c item gets to the heap with priority \c value independently |
|
130 /// if \c item was already there. |
|
131 /// |
|
132 /// This method calls \ref push(\c item, \c value) if \c item is not |
|
133 /// stored in the heap and it calls \ref decrease(\c item, \c value) or |
|
134 /// \ref increase(\c item, \c value) otherwise. |
|
135 void set (const Item& item, const Prio& value) { |
|
136 int i=iimap[item]; |
|
137 if ( i >= 0 && container[i].in ) { |
|
138 if ( comp(value, container[i].prio) ) decrease(item, value); |
|
139 if ( comp(container[i].prio, value) ) increase(item, value); |
|
140 } else push(item, value); |
|
141 } |
|
142 |
|
143 /// \brief Adds \c item to the heap with priority \c value. |
|
144 /// |
|
145 /// Adds \c item to the heap with priority \c value. |
|
146 /// \pre \c item must not be stored in the heap. |
|
147 void push (const Item& item, const Prio& value) { |
|
148 int i=iimap[item]; |
|
149 if ( i<0 ) { |
|
150 int s=container.size(); |
|
151 iimap.set( item,s ); |
|
152 store st; |
|
153 st.name=item; |
|
154 container.push_back(st); |
|
155 i=s; |
|
156 } |
|
157 else { |
|
158 container[i].parent=container[i].right_neighbor=container[i].child=-1; |
|
159 container[i].degree=0; |
|
160 container[i].in=true; |
|
161 } |
|
162 container[i].prio=value; |
|
163 |
|
164 if( 0==num_items ) { head=i; minimum=i; } |
|
165 else { merge(i); } |
|
166 |
|
167 minimum = find_min(); |
|
168 |
|
169 ++num_items; |
|
170 } |
|
171 |
|
172 /// \brief Returns the item with minimum priority relative to \c Compare. |
|
173 /// |
|
174 /// This method returns the item with minimum priority relative to \c |
|
175 /// Compare. |
|
176 /// \pre The heap must be nonempty. |
|
177 Item top() const { return container[minimum].name; } |
|
178 |
|
179 /// \brief Returns the minimum priority relative to \c Compare. |
|
180 /// |
|
181 /// It returns the minimum priority relative to \c Compare. |
|
182 /// \pre The heap must be nonempty. |
|
183 const Prio& prio() const { return container[minimum].prio; } |
|
184 |
|
185 /// \brief Returns the priority of \c item. |
|
186 /// |
|
187 /// It returns the priority of \c item. |
|
188 /// \pre \c item must be in the heap. |
|
189 const Prio& operator[](const Item& item) const { |
|
190 return container[iimap[item]].prio; |
|
191 } |
|
192 |
|
193 /// \brief Deletes the item with minimum priority relative to \c Compare. |
|
194 /// |
|
195 /// This method deletes the item with minimum priority relative to \c |
|
196 /// Compare from the heap. |
|
197 /// \pre The heap must be non-empty. |
|
198 void pop() { |
|
199 container[minimum].in=false; |
|
200 |
|
201 int head_child=-1; |
|
202 if ( container[minimum].child!=-1 ) { |
|
203 int child=container[minimum].child; |
|
204 int neighb; |
|
205 int prev=-1; |
|
206 while( child!=-1 ) { |
|
207 neighb=container[child].right_neighbor; |
|
208 container[child].parent=-1; |
|
209 container[child].right_neighbor=prev; |
|
210 head_child=child; |
|
211 prev=child; |
|
212 child=neighb; |
|
213 } |
|
214 } |
|
215 |
|
216 // The first case is that there are only one root. |
|
217 if ( -1==container[head].right_neighbor ) { |
|
218 head=head_child; |
|
219 } |
|
220 // The case where there are more roots. |
|
221 else { |
|
222 if( head!=minimum ) { unlace(minimum); } |
|
223 else { head=container[head].right_neighbor; } |
|
224 |
|
225 merge(head_child); |
|
226 } |
|
227 minimum=find_min(); |
|
228 --num_items; |
|
229 } |
|
230 |
|
231 /// \brief Deletes \c item from the heap. |
|
232 /// |
|
233 /// This method deletes \c item from the heap, if \c item was already |
|
234 /// stored in the heap. It is quite inefficient in Binomial heaps. |
|
235 void erase (const Item& item) { |
|
236 int i=iimap[item]; |
|
237 if ( i >= 0 && container[i].in ) { |
|
238 decrease( item, container[minimum].prio-1 ); |
|
239 pop(); |
|
240 } |
|
241 } |
|
242 |
|
243 /// \brief Decreases the priority of \c item to \c value. |
|
244 /// |
|
245 /// This method decreases the priority of \c item to \c value. |
|
246 /// \pre \c item must be stored in the heap with priority at least \c |
|
247 /// value relative to \c Compare. |
|
248 void decrease (Item item, const Prio& value) { |
|
249 int i=iimap[item]; |
|
250 |
|
251 if( comp( value,container[i].prio ) ) { |
|
252 container[i].prio=value; |
|
253 |
|
254 int p_loc=container[i].parent, loc=i; |
|
255 int parent, child, neighb; |
|
256 |
|
257 while( -1!=p_loc && comp(container[loc].prio,container[p_loc].prio) ) { |
|
258 |
|
259 // parent set for other loc_child |
|
260 child=container[loc].child; |
|
261 while( -1!=child ) { |
|
262 container[child].parent=p_loc; |
|
263 child=container[child].right_neighbor; |
|
264 } |
|
265 |
|
266 // parent set for other p_loc_child |
|
267 child=container[p_loc].child; |
|
268 while( -1!=child ) { |
|
269 container[child].parent=loc; |
|
270 child=container[child].right_neighbor; |
|
271 } |
|
272 |
|
273 child=container[p_loc].child; |
|
274 container[p_loc].child=container[loc].child; |
|
275 if( child==loc ) |
|
276 child=p_loc; |
|
277 container[loc].child=child; |
|
278 |
|
279 // left_neighb set for p_loc |
|
280 if( container[loc].child!=p_loc ) { |
|
281 while( container[child].right_neighbor!=loc ) |
|
282 child=container[child].right_neighbor; |
|
283 container[child].right_neighbor=p_loc; |
|
284 } |
|
285 |
|
286 // left_neighb set for loc |
|
287 parent=container[p_loc].parent; |
|
288 if( -1!=parent ) child=container[parent].child; |
|
289 else child=head; |
|
290 |
|
291 if( child!=p_loc ) { |
|
292 while( container[child].right_neighbor!=p_loc ) |
|
293 child=container[child].right_neighbor; |
|
294 container[child].right_neighbor=loc; |
|
295 } |
|
296 |
|
297 neighb=container[p_loc].right_neighbor; |
|
298 container[p_loc].right_neighbor=container[loc].right_neighbor; |
|
299 container[loc].right_neighbor=neighb; |
|
300 |
|
301 container[p_loc].parent=loc; |
|
302 container[loc].parent=parent; |
|
303 |
|
304 if( -1!=parent && container[parent].child==p_loc ) |
|
305 container[parent].child=loc; |
|
306 |
|
307 /*if new parent will be the first root*/ |
|
308 if( head==p_loc ) |
|
309 head=loc; |
|
310 |
|
311 p_loc=container[loc].parent; |
|
312 } |
|
313 } |
|
314 if( comp(value,container[minimum].prio) ) { |
|
315 minimum=i; |
|
316 } |
|
317 } |
|
318 |
|
319 /// \brief Increases the priority of \c item to \c value. |
|
320 /// |
|
321 /// This method sets the priority of \c item to \c value. Though |
|
322 /// there is no precondition on the priority of \c item, this |
|
323 /// method should be used only if it is indeed necessary to increase |
|
324 /// (relative to \c Compare) the priority of \c item, because this |
|
325 /// method is inefficient. |
|
326 void increase (Item item, const Prio& value) { |
|
327 erase(item); |
|
328 push(item, value); |
|
329 } |
|
330 |
|
331 |
|
332 /// \brief Returns if \c item is in, has already been in, or has never |
|
333 /// been in the heap. |
|
334 /// |
|
335 /// This method returns PRE_HEAP if \c item has never been in the |
|
336 /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP |
|
337 /// otherwise. In the latter case it is possible that \c item will |
|
338 /// get back to the heap again. |
|
339 State state(const Item &item) const { |
|
340 int i=iimap[item]; |
|
341 if( i>=0 ) { |
|
342 if ( container[i].in ) i=0; |
|
343 else i=-2; |
|
344 } |
|
345 return State(i); |
|
346 } |
|
347 |
|
348 /// \brief Sets the state of the \c item in the heap. |
|
349 /// |
|
350 /// Sets the state of the \c item in the heap. It can be used to |
|
351 /// manually clear the heap when it is important to achive the |
|
352 /// better time complexity. |
|
353 /// \param i The item. |
|
354 /// \param st The state. It should not be \c IN_HEAP. |
|
355 void state(const Item& i, State st) { |
|
356 switch (st) { |
|
357 case POST_HEAP: |
|
358 case PRE_HEAP: |
|
359 if (state(i) == IN_HEAP) { |
|
360 erase(i); |
|
361 } |
|
362 iimap[i] = st; |
|
363 break; |
|
364 case IN_HEAP: |
|
365 break; |
|
366 } |
|
367 } |
|
368 |
|
369 private: |
|
370 int find_min() { |
|
371 int min_loc=-1, min_val; |
|
372 int x=head; |
|
373 if( x!=-1 ) { |
|
374 min_val=container[x].prio; |
|
375 min_loc=x; |
|
376 x=container[x].right_neighbor; |
|
377 |
|
378 while( x!=-1 ) { |
|
379 if( comp( container[x].prio,min_val ) ) { |
|
380 min_val=container[x].prio; |
|
381 min_loc=x; |
|
382 } |
|
383 x=container[x].right_neighbor; |
|
384 } |
|
385 } |
|
386 return min_loc; |
|
387 } |
|
388 |
|
389 void merge(int a) { |
|
390 interleave(a); |
|
391 |
|
392 int x=head; |
|
393 if( -1!=x ) { |
|
394 int x_prev=-1, x_next=container[x].right_neighbor; |
|
395 while( -1!=x_next ) { |
|
396 if( container[x].degree!=container[x_next].degree || ( -1!=container[x_next].right_neighbor && container[container[x_next].right_neighbor].degree==container[x].degree ) ) { |
|
397 x_prev=x; |
|
398 x=x_next; |
|
399 } |
|
400 else { |
|
401 if( comp(container[x].prio,container[x_next].prio) ) { |
|
402 container[x].right_neighbor=container[x_next].right_neighbor; |
|
403 fuse(x_next,x); |
|
404 } |
|
405 else { |
|
406 if( -1==x_prev ) { head=x_next; } |
|
407 else { |
|
408 container[x_prev].right_neighbor=x_next; |
|
409 } |
|
410 fuse(x,x_next); |
|
411 x=x_next; |
|
412 } |
|
413 } |
|
414 x_next=container[x].right_neighbor; |
|
415 } |
|
416 } |
|
417 } |
|
418 |
|
419 void interleave(int a) { |
|
420 int other=-1, head_other=-1; |
|
421 |
|
422 while( -1!=a || -1!=head ) { |
|
423 if( -1==a ) { |
|
424 if( -1==head_other ) { |
|
425 head_other=head; |
|
426 } |
|
427 else { |
|
428 container[other].right_neighbor=head; |
|
429 } |
|
430 head=-1; |
|
431 } |
|
432 else if( -1==head ) { |
|
433 if( -1==head_other ) { |
|
434 head_other=a; |
|
435 } |
|
436 else { |
|
437 container[other].right_neighbor=a; |
|
438 } |
|
439 a=-1; |
|
440 } |
|
441 else { |
|
442 if( container[a].degree<container[head].degree ) { |
|
443 if( -1==head_other ) { |
|
444 head_other=a; |
|
445 } |
|
446 else { |
|
447 container[other].right_neighbor=a; |
|
448 } |
|
449 other=a; |
|
450 a=container[a].right_neighbor; |
|
451 } |
|
452 else { |
|
453 if( -1==head_other ) { |
|
454 head_other=head; |
|
455 } |
|
456 else { |
|
457 container[other].right_neighbor=head; |
|
458 } |
|
459 other=head; |
|
460 head=container[head].right_neighbor; |
|
461 } |
|
462 } |
|
463 } |
|
464 head=head_other; |
|
465 } |
|
466 |
|
467 // Lacing a under b |
|
468 void fuse(int a, int b) { |
|
469 container[a].parent=b; |
|
470 container[a].right_neighbor=container[b].child; |
|
471 container[b].child=a; |
|
472 |
|
473 ++container[b].degree; |
|
474 } |
|
475 |
|
476 // It is invoked only if a has siblings. |
|
477 void unlace(int a) { |
|
478 int neighb=container[a].right_neighbor; |
|
479 int other=head; |
|
480 |
|
481 while( container[other].right_neighbor!=a ) |
|
482 other=container[other].right_neighbor; |
|
483 container[other].right_neighbor=neighb; |
|
484 } |
|
485 |
|
486 private: |
|
487 |
|
488 class store { |
|
489 friend class BinomHeap; |
|
490 |
|
491 Item name; |
|
492 int parent; |
|
493 int right_neighbor; |
|
494 int child; |
|
495 int degree; |
|
496 bool in; |
|
497 Prio prio; |
|
498 |
|
499 store() : parent(-1), right_neighbor(-1), child(-1), degree(0), in(true) {} |
|
500 }; |
|
501 }; |
|
502 |
|
503 } //namespace lemon |
|
504 |
|
505 #endif //LEMON_BINOM_HEAP_H |
|
506 |