首页 > 试题广场 >

试分析在使用下列循环不变量时,HEAP-INCREASE-K

[问答题]
试分析在使用下列循环不变量时,HEAP-INCREASE-KEY的正确性:
      在算法的第4~6行while循环每次迭代开始的时候,子数组A[1...A.heap-size]要满足最大堆的性质。如果有违背,只有一个可能:A[i]大于A[1...A.heap-size]。
这里,你可以假定在调用HEAP-INCREASE-KEY时,A[1...A.heap-size]是满足最大堆性质的。

void HEAP_INCREASE_KEY(int A[],int i,int key)
{
    if (key<A[i])
    {
        return ;
    }
    A[i]=key;
    while (i>0&&A[PARENT(i)]<=key)
    {
        //swap(A[i],A[PARENT(i)]);
        A[i]=A[PARENT(i)];
        i=PARENT(i);
    }
    A[i]=key;
}

这道题你会答吗?花几分钟告诉大家答案吧!