206 |
209 |
207 int head_child=-1; |
210 int head_child=-1; |
208 if ( _data[_min].child!=-1 ) { |
211 if ( _data[_min].child!=-1 ) { |
209 int child=_data[_min].child; |
212 int child=_data[_min].child; |
210 int neighb; |
213 int neighb; |
211 int prev=-1; |
|
212 while( child!=-1 ) { |
214 while( child!=-1 ) { |
213 neighb=_data[child].right_neighbor; |
215 neighb=_data[child].right_neighbor; |
214 _data[child].parent=-1; |
216 _data[child].parent=-1; |
215 _data[child].right_neighbor=prev; |
217 _data[child].right_neighbor=head_child; |
216 head_child=child; |
218 head_child=child; |
217 prev=child; |
|
218 child=neighb; |
219 child=neighb; |
219 } |
220 } |
220 } |
221 } |
221 |
222 |
222 // The first case is that there are only one root. |
223 if ( _data[_head].right_neighbor==-1 ) { |
223 if ( -1==_data[_head].right_neighbor ) { |
224 // there was only one root |
224 _head=head_child; |
225 _head=head_child; |
225 } |
226 } |
226 // The case where there are more roots. |
|
227 else { |
227 else { |
|
228 // there were more roots |
228 if( _head!=_min ) { unlace(_min); } |
229 if( _head!=_min ) { unlace(_min); } |
229 else { _head=_data[_head].right_neighbor; } |
230 else { _head=_data[_head].right_neighbor; } |
230 |
|
231 merge(head_child); |
231 merge(head_child); |
232 } |
232 } |
233 _min=findMin(); |
233 _min=findMin(); |
234 --_num_items; |
234 --_num_items; |
235 } |
235 } |
254 /// \param item The item. |
254 /// \param item The item. |
255 /// \param value The priority. |
255 /// \param value The priority. |
256 /// \pre \e item must be stored in the heap with priority at least \e value. |
256 /// \pre \e item must be stored in the heap with priority at least \e value. |
257 void decrease (Item item, const Prio& value) { |
257 void decrease (Item item, const Prio& value) { |
258 int i=_iim[item]; |
258 int i=_iim[item]; |
259 |
259 int p=_data[i].parent; |
260 if( _comp( value,_data[i].prio ) ) { |
260 _data[i].prio=value; |
261 _data[i].prio=value; |
261 |
262 |
262 while( p!=-1 && _comp(value, _data[p].prio) ) { |
263 int p_loc=_data[i].parent, loc=i; |
263 _data[i].name=_data[p].name; |
264 int parent, child, neighb; |
264 _data[i].prio=_data[p].prio; |
265 |
265 _data[p].name=item; |
266 while( -1!=p_loc && _comp(_data[loc].prio,_data[p_loc].prio) ) { |
266 _data[p].prio=value; |
267 |
267 _iim[_data[i].name]=i; |
268 // parent set for other loc_child |
268 i=p; |
269 child=_data[loc].child; |
269 p=_data[p].parent; |
270 while( -1!=child ) { |
270 } |
271 _data[child].parent=p_loc; |
271 _iim[item]=i; |
272 child=_data[child].right_neighbor; |
272 if ( _comp(value, _data[_min].prio) ) _min=i; |
273 } |
|
274 |
|
275 // parent set for other p_loc_child |
|
276 child=_data[p_loc].child; |
|
277 while( -1!=child ) { |
|
278 _data[child].parent=loc; |
|
279 child=_data[child].right_neighbor; |
|
280 } |
|
281 |
|
282 child=_data[p_loc].child; |
|
283 _data[p_loc].child=_data[loc].child; |
|
284 if( child==loc ) |
|
285 child=p_loc; |
|
286 _data[loc].child=child; |
|
287 |
|
288 // left_neighb set for p_loc |
|
289 if( _data[loc].child!=p_loc ) { |
|
290 while( _data[child].right_neighbor!=loc ) |
|
291 child=_data[child].right_neighbor; |
|
292 _data[child].right_neighbor=p_loc; |
|
293 } |
|
294 |
|
295 // left_neighb set for loc |
|
296 parent=_data[p_loc].parent; |
|
297 if( -1!=parent ) child=_data[parent].child; |
|
298 else child=_head; |
|
299 |
|
300 if( child!=p_loc ) { |
|
301 while( _data[child].right_neighbor!=p_loc ) |
|
302 child=_data[child].right_neighbor; |
|
303 _data[child].right_neighbor=loc; |
|
304 } |
|
305 |
|
306 neighb=_data[p_loc].right_neighbor; |
|
307 _data[p_loc].right_neighbor=_data[loc].right_neighbor; |
|
308 _data[loc].right_neighbor=neighb; |
|
309 |
|
310 _data[p_loc].parent=loc; |
|
311 _data[loc].parent=parent; |
|
312 |
|
313 if( -1!=parent && _data[parent].child==p_loc ) |
|
314 _data[parent].child=loc; |
|
315 |
|
316 /*if new parent will be the first root*/ |
|
317 if( _head==p_loc ) |
|
318 _head=loc; |
|
319 |
|
320 p_loc=_data[loc].parent; |
|
321 } |
|
322 } |
|
323 if( _comp(value,_data[_min].prio) ) { |
|
324 _min=i; |
|
325 } |
|
326 } |
273 } |
327 |
274 |
328 /// \brief Increase the priority of an item to the given value. |
275 /// \brief Increase the priority of an item to the given value. |
329 /// |
276 /// |
330 /// This function increases the priority of an item to the given value. |
277 /// This function increases the priority of an item to the given value. |
373 break; |
320 break; |
374 } |
321 } |
375 } |
322 } |
376 |
323 |
377 private: |
324 private: |
|
325 |
|
326 // Find the minimum of the roots |
378 int findMin() { |
327 int findMin() { |
379 int min_loc=-1, min_val; |
328 if( _head!=-1 ) { |
380 int x=_head; |
329 int min_loc=_head, min_val=_data[_head].prio; |
381 if( x!=-1 ) { |
330 for( int x=_data[_head].right_neighbor; x!=-1; |
382 min_val=_data[x].prio; |
331 x=_data[x].right_neighbor ) { |
383 min_loc=x; |
|
384 x=_data[x].right_neighbor; |
|
385 |
|
386 while( x!=-1 ) { |
|
387 if( _comp( _data[x].prio,min_val ) ) { |
332 if( _comp( _data[x].prio,min_val ) ) { |
388 min_val=_data[x].prio; |
333 min_val=_data[x].prio; |
389 min_loc=x; |
334 min_loc=x; |
390 } |
335 } |
391 x=_data[x].right_neighbor; |
336 } |
392 } |
337 return min_loc; |
393 } |
338 } |
394 return min_loc; |
339 else return -1; |
395 } |
340 } |
396 |
341 |
|
342 // Merge the heap with another heap starting at the given position |
397 void merge(int a) { |
343 void merge(int a) { |
398 interleave(a); |
344 if( _head==-1 || a==-1 ) return; |
399 |
345 if( _data[a].right_neighbor==-1 && |
|
346 _data[a].degree<=_data[_head].degree ) { |
|
347 _data[a].right_neighbor=_head; |
|
348 _head=a; |
|
349 } else { |
|
350 interleave(a); |
|
351 } |
|
352 if( _data[_head].right_neighbor==-1 ) return; |
|
353 |
400 int x=_head; |
354 int x=_head; |
401 if( -1!=x ) { |
355 int x_prev=-1, x_next=_data[x].right_neighbor; |
402 int x_prev=-1, x_next=_data[x].right_neighbor; |
356 while( x_next!=-1 ) { |
403 while( -1!=x_next ) { |
357 if( _data[x].degree!=_data[x_next].degree || |
404 if( _data[x].degree!=_data[x_next].degree || ( -1!=_data[x_next].right_neighbor && _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) { |
358 ( _data[x_next].right_neighbor!=-1 && |
405 x_prev=x; |
359 _data[_data[x_next].right_neighbor].degree==_data[x].degree ) ) { |
|
360 x_prev=x; |
|
361 x=x_next; |
|
362 } |
|
363 else { |
|
364 if( _comp(_data[x_next].prio,_data[x].prio) ) { |
|
365 if( x_prev==-1 ) { |
|
366 _head=x_next; |
|
367 } else { |
|
368 _data[x_prev].right_neighbor=x_next; |
|
369 } |
|
370 fuse(x,x_next); |
406 x=x_next; |
371 x=x_next; |
407 } |
372 } |
408 else { |
373 else { |
409 if( _comp(_data[x].prio,_data[x_next].prio) ) { |
374 _data[x].right_neighbor=_data[x_next].right_neighbor; |
410 _data[x].right_neighbor=_data[x_next].right_neighbor; |
375 fuse(x_next,x); |
411 fuse(x_next,x); |
|
412 } |
|
413 else { |
|
414 if( -1==x_prev ) { _head=x_next; } |
|
415 else { |
|
416 _data[x_prev].right_neighbor=x_next; |
|
417 } |
|
418 fuse(x,x_next); |
|
419 x=x_next; |
|
420 } |
|
421 } |
376 } |
422 x_next=_data[x].right_neighbor; |
377 } |
423 } |
378 x_next=_data[x].right_neighbor; |
424 } |
379 } |
425 } |
380 } |
426 |
381 |
|
382 // Interleave the elements of the given list into the list of the roots |
427 void interleave(int a) { |
383 void interleave(int a) { |
428 int other=-1, head_other=-1; |
384 int p=_head, q=a; |
429 |
385 int curr=_data.size(); |
430 while( -1!=a || -1!=_head ) { |
386 _data.push_back(Store()); |
431 if( -1==a ) { |
387 |
432 if( -1==head_other ) { |
388 while( p!=-1 || q!=-1 ) { |
433 head_other=_head; |
389 if( q==-1 || ( p!=-1 && _data[p].degree<_data[q].degree ) ) { |
434 } |
390 _data[curr].right_neighbor=p; |
435 else { |
391 curr=p; |
436 _data[other].right_neighbor=_head; |
392 p=_data[p].right_neighbor; |
437 } |
|
438 _head=-1; |
|
439 } |
|
440 else if( -1==_head ) { |
|
441 if( -1==head_other ) { |
|
442 head_other=a; |
|
443 } |
|
444 else { |
|
445 _data[other].right_neighbor=a; |
|
446 } |
|
447 a=-1; |
|
448 } |
393 } |
449 else { |
394 else { |
450 if( _data[a].degree<_data[_head].degree ) { |
395 _data[curr].right_neighbor=q; |
451 if( -1==head_other ) { |
396 curr=q; |
452 head_other=a; |
397 q=_data[q].right_neighbor; |
453 } |
398 } |
454 else { |
399 } |
455 _data[other].right_neighbor=a; |
400 |
456 } |
401 _head=_data.back().right_neighbor; |
457 other=a; |
402 _data.pop_back(); |
458 a=_data[a].right_neighbor; |
403 } |
459 } |
404 |
460 else { |
405 // Lace node a under node b |
461 if( -1==head_other ) { |
|
462 head_other=_head; |
|
463 } |
|
464 else { |
|
465 _data[other].right_neighbor=_head; |
|
466 } |
|
467 other=_head; |
|
468 _head=_data[_head].right_neighbor; |
|
469 } |
|
470 } |
|
471 } |
|
472 _head=head_other; |
|
473 } |
|
474 |
|
475 // Lacing a under b |
|
476 void fuse(int a, int b) { |
406 void fuse(int a, int b) { |
477 _data[a].parent=b; |
407 _data[a].parent=b; |
478 _data[a].right_neighbor=_data[b].child; |
408 _data[a].right_neighbor=_data[b].child; |
479 _data[b].child=a; |
409 _data[b].child=a; |
480 |
410 |
481 ++_data[b].degree; |
411 ++_data[b].degree; |
482 } |
412 } |
483 |
413 |
484 // It is invoked only if a has siblings. |
414 // Unlace node a (if it has siblings) |
485 void unlace(int a) { |
415 void unlace(int a) { |
486 int neighb=_data[a].right_neighbor; |
416 int neighb=_data[a].right_neighbor; |
487 int other=_head; |
417 int other=_head; |
488 |
418 |
489 while( _data[other].right_neighbor!=a ) |
419 while( _data[other].right_neighbor!=a ) |