206 /// \brief Remove the item having minimum priority. |
206 /// \brief Remove the item having minimum priority. |
207 /// |
207 /// |
208 /// This function removes the item having minimum priority. |
208 /// This function removes the item having minimum priority. |
209 /// \pre The heap must be non-empty. |
209 /// \pre The heap must be non-empty. |
210 void pop() { |
210 void pop() { |
211 int TreeArray[_num_items]; |
211 std::vector<int> trees; |
212 int i=0, num_child=0, child_right = 0; |
212 int i=0, child_right = 0; |
213 _data[_min].in=false; |
213 _data[_min].in=false; |
214 |
214 |
215 if( -1!=_data[_min].child ) { |
215 if( -1!=_data[_min].child ) { |
216 i=_data[_min].child; |
216 i=_data[_min].child; |
217 TreeArray[num_child] = i; |
217 trees.push_back(i); |
218 _data[i].parent = -1; |
218 _data[i].parent = -1; |
219 _data[_min].child = -1; |
219 _data[_min].child = -1; |
220 |
220 |
221 ++num_child; |
|
222 int ch=-1; |
221 int ch=-1; |
223 while( _data[i].child!=-1 ) { |
222 while( _data[i].child!=-1 ) { |
224 ch=_data[i].child; |
223 ch=_data[i].child; |
225 if( _data[ch].left_child && i==_data[ch].parent ) { |
224 if( _data[ch].left_child && i==_data[ch].parent ) { |
226 i=ch; |
225 break; |
227 //break; |
|
228 } else { |
226 } else { |
229 if( _data[ch].left_child ) { |
227 if( _data[ch].left_child ) { |
230 child_right=_data[ch].parent; |
228 child_right=_data[ch].parent; |
231 _data[ch].parent = i; |
229 _data[ch].parent = i; |
232 --_data[i].degree; |
230 --_data[i].degree; |
235 child_right=ch; |
233 child_right=ch; |
236 _data[i].child=-1; |
234 _data[i].child=-1; |
237 _data[i].degree=0; |
235 _data[i].degree=0; |
238 } |
236 } |
239 _data[child_right].parent = -1; |
237 _data[child_right].parent = -1; |
240 TreeArray[num_child] = child_right; |
238 trees.push_back(child_right); |
241 i = child_right; |
239 i = child_right; |
242 ++num_child; |
240 } |
243 } |
241 } |
244 } |
242 |
245 |
243 int num_child = trees.size(); |
246 int other; |
244 int other; |
247 for( i=0; i<num_child-1; i+=2 ) { |
245 for( i=0; i<num_child-1; i+=2 ) { |
248 if ( !_comp(_data[TreeArray[i]].prio, |
246 if ( !_comp(_data[trees[i]].prio, _data[trees[i+1]].prio) ) { |
249 _data[TreeArray[i+1]].prio) ) { |
247 other=trees[i]; |
250 other=TreeArray[i]; |
248 trees[i]=trees[i+1]; |
251 TreeArray[i]=TreeArray[i+1]; |
249 trees[i+1]=other; |
252 TreeArray[i+1]=other; |
250 } |
253 } |
251 fuse( trees[i], trees[i+1] ); |
254 fuse( TreeArray[i], TreeArray[i+1] ); |
|
255 } |
252 } |
256 |
253 |
257 i = (0==(num_child % 2)) ? num_child-2 : num_child-1; |
254 i = (0==(num_child % 2)) ? num_child-2 : num_child-1; |
258 while(i>=2) { |
255 while(i>=2) { |
259 if ( _comp(_data[TreeArray[i]].prio, |
256 if ( _comp(_data[trees[i]].prio, _data[trees[i-2]].prio) ) { |
260 _data[TreeArray[i-2]].prio) ) { |
257 other=trees[i]; |
261 other=TreeArray[i]; |
258 trees[i]=trees[i-2]; |
262 TreeArray[i]=TreeArray[i-2]; |
259 trees[i-2]=other; |
263 TreeArray[i-2]=other; |
260 } |
264 } |
261 fuse( trees[i-2], trees[i] ); |
265 fuse( TreeArray[i-2], TreeArray[i] ); |
|
266 i-=2; |
262 i-=2; |
267 } |
263 } |
268 _min = TreeArray[0]; |
264 _min = trees[0]; |
269 } |
265 } |
270 |
266 else { |
271 if ( 0==num_child ) { |
|
272 _min = _data[_min].child; |
267 _min = _data[_min].child; |
273 } |
268 } |
274 |
269 |
275 if (_min >= 0) _data[_min].left_child = false; |
270 if (_min >= 0) _data[_min].left_child = false; |
276 |
|
277 --_num_items; |
271 --_num_items; |
278 } |
272 } |
279 |
273 |
280 /// \brief Remove the given item from the heap. |
274 /// \brief Remove the given item from the heap. |
281 /// |
275 /// |