19 * in the heap, and calls decrease/increase(Item, Prio) otherwise |
19 * in the heap, and calls decrease/increase(Item, Prio) otherwise |
20 * |
20 * |
21 *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item |
21 *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item |
22 * mustn't be in the heap. |
22 * mustn't be in the heap. |
23 * |
23 * |
24 *Item top() : returns the Item with least Prio |
24 *Item top() : returns the Item with least Prio. |
|
25 * Must be called only if heap is nonempty. |
25 * |
26 * |
26 *Prio prio() : returns the least Prio |
27 *Prio prio() : returns the least Prio |
27 * |
28 * Must be called only if heap is nonempty. |
|
29 * |
28 *Prio get(Item) : returns Prio of Item |
30 *Prio get(Item) : returns Prio of Item |
|
31 * Must be called only if Item is in heap. |
29 * |
32 * |
30 *void pop() : deletes the Item with least Prio |
33 *void pop() : deletes the Item with least Prio |
31 * |
34 * |
32 *void erase(Item) : deletes Item from the heap if it was already there |
35 *void erase(Item) : deletes Item from the heap if it was already there |
33 * |
36 * |
63 |
66 |
64 class store; |
67 class store; |
65 |
68 |
66 std::vector<store> container; |
69 std::vector<store> container; |
67 int minimum; |
70 int minimum; |
68 bool blank; |
|
69 ItemIntMap &iimap; |
71 ItemIntMap &iimap; |
70 Compare comp; |
72 Compare comp; |
|
73 int num_items; |
71 |
74 |
72 enum state_enum { |
75 enum state_enum { |
73 IN_HEAP = 0, |
76 IN_HEAP = 0, |
74 PRE_HEAP = -1, |
77 PRE_HEAP = -1, |
75 POST_HEAP = -2 |
78 POST_HEAP = -2 |
76 }; |
79 }; |
77 |
80 |
78 public : |
81 public : |
79 |
82 |
80 FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {} |
83 FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {} |
81 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), |
84 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(), |
82 blank(true), iimap(_iimap), comp(_comp) {} |
85 iimap(_iimap), comp(_comp), num_items() {} |
83 |
86 |
84 |
87 |
85 int size() const { |
88 int size() const { |
86 int s=0; |
89 return num_items; |
87 for ( unsigned int i=0; i!=container.size(); ++i ) |
90 } |
88 if ( container[i].in ) ++s; |
91 |
89 return s; |
92 |
90 } |
93 bool empty() const { return num_items==0; } |
91 |
|
92 |
|
93 bool empty() const { return blank; } |
|
94 |
94 |
95 |
95 |
96 void set (Item const it, PrioType const value) { |
96 void set (Item const it, PrioType const value) { |
97 int i=iimap.get(it); |
97 int i=iimap.get(it); |
98 if ( i >= 0 && container[i].in ) { |
98 if ( i >= 0 && container[i].in ) { |
99 if ( !comp(container[i].prio, value) ) decrease(it, value); |
99 if ( comp(value, container[i].prio) ) decrease(it, value); |
100 if ( comp(container[i].prio, value) ) increase(it, value); |
100 if ( comp(container[i].prio, value) ) increase(it, value); |
101 } else push(it, value); |
101 } else push(it, value); |
102 } |
102 } |
103 |
103 |
104 |
104 |
116 container[i].degree=0; |
116 container[i].degree=0; |
117 container[i].in=true; |
117 container[i].in=true; |
118 container[i].marked=false; |
118 container[i].marked=false; |
119 } |
119 } |
120 |
120 |
121 if ( !blank ) { |
121 if ( num_items ) { |
122 container[container[minimum].right_neighbor].left_neighbor=i; |
122 container[container[minimum].right_neighbor].left_neighbor=i; |
123 container[i].right_neighbor=container[minimum].right_neighbor; |
123 container[i].right_neighbor=container[minimum].right_neighbor; |
124 container[minimum].right_neighbor=i; |
124 container[minimum].right_neighbor=i; |
125 container[i].left_neighbor=minimum; |
125 container[i].left_neighbor=minimum; |
126 if ( !comp( container[minimum].prio, value) ) minimum=i; |
126 if ( comp( value, container[minimum].prio) ) minimum=i; |
127 } else { |
127 } else { |
128 container[i].right_neighbor=container[i].left_neighbor=i; |
128 container[i].right_neighbor=container[i].left_neighbor=i; |
129 minimum=i; |
129 minimum=i; |
130 blank=false; |
|
131 } |
130 } |
132 container[i].prio=value; |
131 container[i].prio=value; |
|
132 ++num_items; |
133 } |
133 } |
134 |
134 |
135 |
135 |
136 Item top() const { |
136 Item top() const { |
137 if ( !blank ) { |
137 return container[minimum].name; |
138 return container[minimum].name; |
|
139 } else { |
|
140 return Item(); |
|
141 } |
|
142 } |
138 } |
143 |
139 |
144 |
140 |
145 PrioType prio() const { |
141 PrioType prio() const { |
146 if ( !blank ) { |
142 return container[minimum].prio; |
147 return container[minimum].prio; |
|
148 } else { |
|
149 return PrioType(); |
|
150 } |
|
151 } |
143 } |
152 |
144 |
153 |
145 |
154 const PrioType get(const Item& it) const { |
146 const PrioType get(const Item& it) const { |
155 int i=iimap.get(it); |
147 return container[iimap.get(it)].prio; |
156 |
148 } |
157 if ( i >= 0 && container[i].in ) { |
|
158 return container[i].prio; |
|
159 } else { |
|
160 return PrioType(); |
|
161 } |
|
162 } |
|
163 |
|
164 |
|
165 |
149 |
166 |
150 |
167 void pop() { |
151 void pop() { |
168 /*The first case is that there are only one root.*/ |
152 /*The first case is that there are only one root.*/ |
169 if ( container[minimum].left_neighbor==minimum ) { |
153 if ( container[minimum].left_neighbor==minimum ) { |
170 container[minimum].in=false; |
154 container[minimum].in=false; |
171 if ( container[minimum].degree==0 ) blank=true; |
155 if ( container[minimum].degree!=0 ) { |
172 else { |
|
173 makeroot(container[minimum].child); |
156 makeroot(container[minimum].child); |
174 minimum=container[minimum].child; |
157 minimum=container[minimum].child; |
175 balance(); |
158 balance(); |
176 } |
159 } |
177 } else { |
160 } else { |
178 int right=container[minimum].right_neighbor; |
161 int right=container[minimum].right_neighbor; |
179 unlace(minimum); |
162 unlace(minimum); |
180 container[minimum].in=false; |
163 container[minimum].in=false; |
181 if ( container[minimum].degree > 0 ) { |
164 if ( container[minimum].degree > 0 ) { |
191 container[last_child].right_neighbor=right; |
174 container[last_child].right_neighbor=right; |
192 } |
175 } |
193 minimum=right; |
176 minimum=right; |
194 balance(); |
177 balance(); |
195 } // the case where there are more roots |
178 } // the case where there are more roots |
|
179 --num_items; |
196 } |
180 } |
197 |
181 |
198 |
182 |
199 void erase (const Item& it) { |
183 void erase (const Item& it) { |
200 int i=iimap.get(it); |
184 int i=iimap.get(it); |
201 |
185 |
202 if ( i >= 0 && container[i].in ) { |
186 if ( i >= 0 && container[i].in ) { |
203 |
187 if ( container[i].parent!=-1 ) { |
204 if ( container[i].parent!=-1 ) { |
188 int p=container[i].parent; |
205 int p=container[i].parent; |
189 cut(i,p); |
206 cut(i,p); |
190 cascade(p); |
207 cascade(p); |
191 } |
208 minimum=i; //As if its prio would be -infinity |
192 minimum=i; //As if its prio would be -infinity |
209 } |
193 pop(); |
210 pop(); |
194 } |
211 } |
195 } |
212 } |
|
213 |
196 |
214 |
197 |
215 void decrease (Item it, PrioType const value) { |
198 void decrease (Item it, PrioType const value) { |
216 int i=iimap.get(it); |
199 int i=iimap.get(it); |
217 container[i].prio=value; |
200 container[i].prio=value; |
218 int p=container[i].parent; |
201 int p=container[i].parent; |
219 |
202 |
220 if ( p!=-1 && comp(value, container[p].prio) ) { |
203 if ( p!=-1 && comp(value, container[p].prio) ) { |
221 cut(i,p); |
204 cut(i,p); |
222 cascade(p); |
205 cascade(p); |
223 if ( comp(value, container[minimum].prio) ) minimum=i; |
206 } |
224 } |
207 if ( comp(value, container[minimum].prio) ) minimum=i; |
225 } |
208 } |
226 |
209 |
227 |
210 |
228 void increase (Item it, PrioType const value) { |
211 void increase (Item it, PrioType const value) { |
229 erase(it); |
212 erase(it); |
308 container[b].child=container[child].right_neighbor; |
291 container[b].child=container[child].right_neighbor; |
309 unlace(a); |
292 unlace(a); |
310 } |
293 } |
311 |
294 |
312 |
295 |
313 /*Lacing i to the roots.*/ |
296 /*Lacing a to the roots.*/ |
314 int right=container[minimum].right_neighbor; |
297 int right=container[minimum].right_neighbor; |
315 container[minimum].right_neighbor=a; |
298 container[minimum].right_neighbor=a; |
316 container[a].left_neighbor=minimum; |
299 container[a].left_neighbor=minimum; |
317 container[a].right_neighbor=right; |
300 container[a].right_neighbor=right; |
318 container[right].left_neighbor=a; |
301 container[right].left_neighbor=a; |