118 data.clear(); |
118 data.clear(); |
119 } |
119 } |
120 |
120 |
121 private: |
121 private: |
122 static int parent(int i) { return (i-1)/2; } |
122 static int parent(int i) { return (i-1)/2; } |
|
123 |
123 static int second_child(int i) { return 2*i+2; } |
124 static int second_child(int i) { return 2*i+2; } |
124 bool less(const PairType &p1, const PairType &p2) const { |
125 bool less(const PairType &p1, const PairType &p2) const { |
125 return comp(p1.second, p2.second); |
126 return comp(p1.second, p2.second); |
126 } |
127 } |
127 |
128 |
128 int bubble_up(int hole, PairType p); |
129 int bubble_up(int hole, PairType p) { |
129 int bubble_down(int hole, PairType p, int length); |
130 int par = parent(hole); |
|
131 while( hole>0 && less(p,data[par]) ) { |
|
132 move(data[par],hole); |
|
133 hole = par; |
|
134 par = parent(hole); |
|
135 } |
|
136 move(p, hole); |
|
137 return hole; |
|
138 } |
|
139 |
|
140 int bubble_down(int hole, PairType p, int length) { |
|
141 int child = second_child(hole); |
|
142 while(child < length) { |
|
143 if( less(data[child-1], data[child]) ) { |
|
144 --child; |
|
145 } |
|
146 if( !less(data[child], p) ) |
|
147 goto ok; |
|
148 move(data[child], hole); |
|
149 hole = child; |
|
150 child = second_child(hole); |
|
151 } |
|
152 child--; |
|
153 if( child<length && less(data[child], p) ) { |
|
154 move(data[child], hole); |
|
155 hole=child; |
|
156 } |
|
157 ok: |
|
158 move(p, hole); |
|
159 return hole; |
|
160 } |
130 |
161 |
131 void move(const PairType &p, int i) { |
162 void move(const PairType &p, int i) { |
132 data[i] = p; |
163 data[i] = p; |
133 iim.set(p.first, i); |
164 iim.set(p.first, i); |
134 } |
|
135 |
|
136 void rmidx(int h) { |
|
137 int n = data.size()-1; |
|
138 if( h>=0 && h<=n ) { |
|
139 iim.set(data[h].first, POST_HEAP); |
|
140 if ( h<n ) { |
|
141 bubble_down(h, data[n], n); |
|
142 } |
|
143 data.pop_back(); |
|
144 } |
|
145 } |
165 } |
146 |
166 |
147 public: |
167 public: |
148 /// \brief Insert a pair of item and priority into the heap. |
168 /// \brief Insert a pair of item and priority into the heap. |
149 /// |
169 /// |
183 /// |
203 /// |
184 /// This method deletes the item with minimum priority relative to \c |
204 /// This method deletes the item with minimum priority relative to \c |
185 /// Compare from the heap. |
205 /// Compare from the heap. |
186 /// \pre The heap must be non-empty. |
206 /// \pre The heap must be non-empty. |
187 void pop() { |
207 void pop() { |
188 rmidx(0); |
208 int n = data.size()-1; |
|
209 iim.set(data[0].first, POST_HEAP); |
|
210 if (n > 0) { |
|
211 bubble_down(0, data[n], n); |
|
212 } |
|
213 data.pop_back(); |
189 } |
214 } |
190 |
215 |
191 /// \brief Deletes \c i from the heap. |
216 /// \brief Deletes \c i from the heap. |
192 /// |
217 /// |
193 /// This method deletes item \c i from the heap, if \c i was |
218 /// This method deletes item \c i from the heap. |
194 /// already stored in the heap. |
219 /// \param i The item to erase. |
195 /// \param i The item to erase. |
220 /// \pre The item should be in the heap. |
196 void erase(const ItemType &i) { |
221 void erase(const ItemType &i) { |
197 rmidx(iim[i]); |
222 int h = iim[i]; |
|
223 int n = data.size()-1; |
|
224 iim.set(data[h].first, POST_HEAP); |
|
225 if( h < n ) { |
|
226 if ( bubble_up(h, data[n]) == h) { |
|
227 bubble_down(h, data[n], n); |
|
228 } |
|
229 } |
|
230 data.pop_back(); |
198 } |
231 } |
199 |
232 |
200 |
233 |
201 /// \brief Returns the priority of \c i. |
234 /// \brief Returns the priority of \c i. |
202 /// |
235 /// |
287 break; |
320 break; |
288 } |
321 } |
289 } |
322 } |
290 |
323 |
291 }; // class BinHeap |
324 }; // class BinHeap |
292 |
|
293 |
325 |
294 template <typename V, typename M, typename C> |
|
295 int BinHeap<V,M,C>::bubble_up(int hole, PairType p) { |
|
296 int par = parent(hole); |
|
297 while( hole>0 && less(p,data[par]) ) { |
|
298 move(data[par],hole); |
|
299 hole = par; |
|
300 par = parent(hole); |
|
301 } |
|
302 move(p, hole); |
|
303 return hole; |
|
304 } |
|
305 |
|
306 template <typename V, typename M, typename C> |
|
307 int BinHeap<V,M,C>::bubble_down(int hole, PairType p, int length) { |
|
308 int child = second_child(hole); |
|
309 while(child < length) { |
|
310 if( less(data[child-1], data[child]) ) { |
|
311 --child; |
|
312 } |
|
313 if( !less(data[child], p) ) |
|
314 goto ok; |
|
315 move(data[child], hole); |
|
316 hole = child; |
|
317 child = second_child(hole); |
|
318 } |
|
319 child--; |
|
320 if( child<length && less(data[child], p) ) { |
|
321 move(data[child], hole); |
|
322 hole=child; |
|
323 } |
|
324 ok: |
|
325 move(p, hole); |
|
326 return hole; |
|
327 } |
|
328 |
|
329 |
|
330 } // namespace lemon |
326 } // namespace lemon |
331 |
327 |
332 #endif // LEMON_BIN_HEAP_H |
328 #endif // LEMON_BIN_HEAP_H |