关于堆deletemin
以下是摘自Data Structures and Algorithm Analysis in C一书中heaps deletemin的代码,我对line 13有点疑问,如果这里Size就自减了,那line 15 for循环不就可能会提前一次结束了?line 19中Child != H->Size也起不到检查one child的情况?从网上看别人贴的代码都是在line 13就自减了,是不是我对堆队列的Size的理解错了。。还望高手解答,谢谢了~!
ElementType堆?deletemin
DeleteMin( PriorityQueue H )
{
int i, Child;
ElementType MinElement, LastElement;
if( IsEmpty( H ) )
{
printf( "Queue is empty.\n" );
return H->Elements[0];
}
MinElement = H->Elements[1];
LastElement = H->Elements[H->Size--];
for( i = 1; i*2 <= H->Size; i = Child )
{
/* Find smaller child. */
Child = i*2;
if( Child != H->Size && H->Elements[Child+1]
< H->Elements[Child] )
Child++;
/* Perlocate one level. */
if( LastElement > H->Elements[Child] )
H->Elements[i] = H->Elements[Child];
else
break;
}
H->Elements[i] = LastElement;
return MinElement;
}
[解决办法]
>line 19中的Child != H ->Size没有什么用处
这句单纯是为了下一句[Child+1]不溢出。
>我总感觉Size应该放到for循环之后减一
那你for里面不能写<=得写<。