试分析在使用下列循环不变量时,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; }