1 // -*- C++ -*- |
|
2 /* |
|
3 *template <typename Item, |
|
4 * typename Prio, |
|
5 * typename ItemIntMap, |
|
6 * typename Compare = std::less<Prio> > |
|
7 * |
|
8 *constructors: |
|
9 * |
|
10 *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare) |
|
11 * |
|
12 *Member functions: |
|
13 * |
|
14 *int size() : returns the number of elements in the heap |
|
15 * |
|
16 *bool empty() : true iff size()=0 |
|
17 * |
|
18 *void set(Item, Prio) : calls push(Item, Prio) if Item is not |
|
19 * in the heap, and calls decrease/increase(Item, Prio) otherwise |
|
20 * |
|
21 *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item |
|
22 * mustn't be in the heap. |
|
23 * |
|
24 *Item top() : returns the Item with least Prio |
|
25 * |
|
26 *Prio prio() : returns the least Prio |
|
27 * |
|
28 *Prio get(Item) : returns Prio of Item |
|
29 * |
|
30 *void pop() : deletes the Item with least Prio |
|
31 * |
|
32 *void erase(Item) : deletes Item from the heap if it was already there |
|
33 * |
|
34 *void decrease(Item, P) : decreases prio of Item to P. Item must be in the heap |
|
35 * with prio at least P. |
|
36 * |
|
37 *void increase(Item, P) : sets prio of Item to P. |
|
38 * |
|
39 * |
|
40 *In Fibonacci heaps, increase and erase are not efficient, in case of |
|
41 *many calls to these operations, it is better to use bin_heap. |
|
42 */ |
|
43 |
|
44 #ifndef FIB_HEAP_H |
|
45 #define FIB_HEAP_H |
|
46 |
|
47 #include <vector> |
|
48 #include <functional> |
|
49 #include <math.h> |
|
50 |
|
51 namespace hugo { |
|
52 |
|
53 template <typename Item, typename Prio, typename ItemIntMap, |
|
54 typename Compare = std::less<Prio> > |
|
55 |
|
56 class FibHeap { |
|
57 |
|
58 typedef Prio PrioType; |
|
59 |
|
60 class store; |
|
61 |
|
62 std::vector<store> container; |
|
63 int minimum; |
|
64 bool blank; |
|
65 ItemIntMap &iimap; |
|
66 Compare comp; |
|
67 |
|
68 public : |
|
69 |
|
70 FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {} |
|
71 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), |
|
72 blank(true), iimap(_iimap), comp(_comp) {} |
|
73 |
|
74 |
|
75 int size() const { |
|
76 int s=0; |
|
77 for ( unsigned int i=0; i!=container.size(); ++i ) |
|
78 if ( container[i].in ) ++s; |
|
79 return s; |
|
80 } |
|
81 |
|
82 |
|
83 bool empty() const { return blank; } |
|
84 |
|
85 |
|
86 void set (Item const it, PrioType const value) { |
|
87 int i=iimap.get(it); |
|
88 if ( i >= 0 && container[i].in ) { |
|
89 if ( !comp(container[i].prio, value) ) decrease(it, value); |
|
90 if ( comp(container[i].prio, value) ) increase(it, value); |
|
91 } else push(it, value); |
|
92 } |
|
93 |
|
94 |
|
95 void push (Item const it, PrioType const value) { |
|
96 int i=iimap.get(it); |
|
97 if ( i < 0 ) { |
|
98 int s=container.size(); |
|
99 iimap.set( it, s ); |
|
100 store st; |
|
101 st.name=it; |
|
102 container.push_back(st); |
|
103 i=s; |
|
104 } |
|
105 |
|
106 if ( !blank ) { |
|
107 container[container[minimum].right_neighbor].left_neighbor=i; |
|
108 container[i].right_neighbor=container[minimum].right_neighbor; |
|
109 container[minimum].right_neighbor=i; |
|
110 container[i].left_neighbor=minimum; |
|
111 if ( !comp( container[minimum].prio, value) ) minimum=i; |
|
112 |
|
113 } else { |
|
114 container[i].right_neighbor=container[i].left_neighbor=i; |
|
115 minimum=i; |
|
116 blank=false; |
|
117 } |
|
118 container[i].prio=value; |
|
119 } |
|
120 |
|
121 |
|
122 |
|
123 Item top() const { |
|
124 if ( !blank ) { |
|
125 return container[minimum].name; |
|
126 } else { |
|
127 return Item(); |
|
128 } |
|
129 } |
|
130 |
|
131 |
|
132 PrioType prio() const { |
|
133 if ( !blank ) { |
|
134 return container[minimum].prio; |
|
135 } else { |
|
136 return PrioType(); |
|
137 } |
|
138 } |
|
139 |
|
140 |
|
141 const PrioType get(const Item& it) const |
|
142 { |
|
143 int i=iimap.get(it); |
|
144 |
|
145 if ( i >= 0 && container[i].in ) { |
|
146 return container[i].prio; |
|
147 } else { |
|
148 return PrioType(); |
|
149 } |
|
150 } |
|
151 |
|
152 |
|
153 void pop() { |
|
154 if ( !blank ) { |
|
155 |
|
156 /*The first case is that there are only one root.*/ |
|
157 if ( container[minimum].left_neighbor==minimum ) { |
|
158 container[minimum].in=false; |
|
159 if ( container[minimum].degree==0 ) blank=true; |
|
160 else { |
|
161 makeroot(container[minimum].child); |
|
162 minimum=container[minimum].child; |
|
163 balance(); |
|
164 } |
|
165 } else { |
|
166 int right=container[minimum].right_neighbor; |
|
167 unlace(minimum); |
|
168 container[minimum].in=false; |
|
169 if ( container[minimum].degree > 0 ) { |
|
170 int left=container[minimum].left_neighbor; |
|
171 int child=container[minimum].child; |
|
172 int last_child=container[child].left_neighbor; |
|
173 |
|
174 container[left].right_neighbor=child; |
|
175 container[child].left_neighbor=left; |
|
176 container[right].left_neighbor=last_child; |
|
177 container[last_child].right_neighbor=right; |
|
178 |
|
179 makeroot(child); |
|
180 } |
|
181 minimum=right; |
|
182 balance(); |
|
183 } // the case where there are more roots |
|
184 } |
|
185 } |
|
186 |
|
187 |
|
188 void erase (const Item& it) { |
|
189 int i=iimap.get(it); |
|
190 |
|
191 if ( i >= 0 && container[i].in ) { |
|
192 |
|
193 if ( container[i].parent!=-1 ) { |
|
194 int p=container[i].parent; |
|
195 cut(i,p); |
|
196 cascade(p); |
|
197 minimum=i; //As if its prio would be -infinity |
|
198 } |
|
199 pop(); |
|
200 } |
|
201 } |
|
202 |
|
203 |
|
204 void decrease (Item it, PrioType const value) { |
|
205 int i=iimap.get(it); |
|
206 container[i].prio=value; |
|
207 int p=container[i].parent; |
|
208 |
|
209 if ( p!=-1 && comp(value, container[p].prio) ) { |
|
210 cut(i,p); |
|
211 cascade(p); |
|
212 if ( comp(value, container[minimum].prio) ) minimum=i; |
|
213 } |
|
214 } |
|
215 |
|
216 |
|
217 void increase (Item it, PrioType const value) { |
|
218 erase(it); |
|
219 push(it, value); |
|
220 } |
|
221 |
|
222 |
|
223 private: |
|
224 |
|
225 void balance() { |
|
226 int maxdeg=int( floor( 2.08*log(double(container.size()))))+1; |
|
227 |
|
228 std::vector<int> A(maxdeg,-1); |
|
229 |
|
230 /* |
|
231 *Recall that now minimum does not point to the minimum prio element. |
|
232 *We set minimum to this during balance(). |
|
233 */ |
|
234 int anchor=container[minimum].left_neighbor; |
|
235 int next=minimum; |
|
236 bool end=false; |
|
237 |
|
238 do { |
|
239 int active=next; |
|
240 int d=container[active].degree; |
|
241 if ( anchor==active ) end=true; |
|
242 next = container[active].right_neighbor; |
|
243 if ( !comp(container[minimum].prio, container[active].prio) ) |
|
244 minimum=active; |
|
245 |
|
246 while (A[d]!=-1) { |
|
247 |
|
248 if( comp(container[active].prio, container[A[d]].prio) ) { |
|
249 fuse(active,A[d]); |
|
250 } else { |
|
251 fuse(A[d],active); |
|
252 active=A[d]; |
|
253 } |
|
254 A[d]=-1; |
|
255 ++d; |
|
256 } |
|
257 |
|
258 A[d]=active; |
|
259 } while ( !end ); |
|
260 } |
|
261 |
|
262 |
|
263 |
|
264 |
|
265 /* |
|
266 *All the siblings of a are made roots. |
|
267 */ |
|
268 void makeroot (int c) |
|
269 { |
|
270 int s=c; |
|
271 do { |
|
272 container[s].parent=-1; |
|
273 s=container[s].right_neighbor; |
|
274 } while ( s != c ); |
|
275 } |
|
276 |
|
277 |
|
278 void cut (int a, int b) |
|
279 { |
|
280 |
|
281 /* |
|
282 *Replacing a from the children of b. |
|
283 */ |
|
284 --container[b].degree; |
|
285 |
|
286 if ( container[b].degree !=0 ) { |
|
287 int child=container[b].child; |
|
288 if ( child==a ) |
|
289 container[b].child=container[child].right_neighbor; |
|
290 |
|
291 unlace(a); |
|
292 |
|
293 } |
|
294 |
|
295 |
|
296 /*Lacing i to the roots.*/ |
|
297 int right=container[minimum].right_neighbor; |
|
298 container[minimum].right_neighbor=a; |
|
299 container[a].left_neighbor=minimum; |
|
300 container[a].right_neighbor=right; |
|
301 container[right].left_neighbor=a; |
|
302 |
|
303 container[a].parent=-1; |
|
304 container[a].marked=false; |
|
305 } |
|
306 |
|
307 |
|
308 void cascade (int a) |
|
309 { |
|
310 if ( container[a].parent!=-1 ) { |
|
311 int p=container[a].parent; |
|
312 |
|
313 if ( container[a].marked==false ) container[a].marked=true; |
|
314 else { |
|
315 cut(a,p); |
|
316 cascade(p); |
|
317 } |
|
318 } |
|
319 } |
|
320 |
|
321 |
|
322 void fuse (int a, int b) |
|
323 { |
|
324 |
|
325 unlace(b); |
|
326 |
|
327 |
|
328 /*Lacing b under a.*/ |
|
329 container[b].parent=a; |
|
330 |
|
331 if (container[a].degree==0) { |
|
332 container[b].left_neighbor=b; |
|
333 container[b].right_neighbor=b; |
|
334 container[a].child=b; |
|
335 } else { |
|
336 int child=container[a].child; |
|
337 int last_child=container[child].left_neighbor; |
|
338 container[child].left_neighbor=b; |
|
339 container[b].right_neighbor=child; |
|
340 container[last_child].right_neighbor=b; |
|
341 container[b].left_neighbor=last_child; |
|
342 } |
|
343 |
|
344 ++container[a].degree; |
|
345 |
|
346 container[b].marked=false; |
|
347 } |
|
348 |
|
349 |
|
350 /* |
|
351 *It is invoked only if a has siblings. |
|
352 */ |
|
353 |
|
354 void unlace (int a) { |
|
355 int leftn=container[a].left_neighbor; |
|
356 int rightn=container[a].right_neighbor; |
|
357 container[leftn].right_neighbor=rightn; |
|
358 container[rightn].left_neighbor=leftn; |
|
359 } |
|
360 |
|
361 |
|
362 class store { |
|
363 friend class FibHeap; |
|
364 |
|
365 Item name; |
|
366 int parent; |
|
367 int left_neighbor; |
|
368 int right_neighbor; |
|
369 int child; |
|
370 int degree; |
|
371 bool marked; |
|
372 bool in; |
|
373 PrioType prio; |
|
374 |
|
375 store() : parent(-1), child(-1), degree(), marked(false), in(true) {} |
|
376 }; |
|
377 |
|
378 }; |
|
379 |
|
380 } //namespace hugo |
|
381 #endif |
|
382 |
|
383 |
|
384 |
|
385 |
|
386 |
|
387 |
|