已知关键字序列(K1,K2,K3,…,Kn-1)是大根堆。试写出一算法将(K1,K2,K3,…,Kn-1,Kn)调整为大根堆,并利用调整算法写一个建大根堆的算法。

admin2019-08-01  13

问题 已知关键字序列(K1,K2,K3,…,Kn-1)是大根堆。试写出一算法将(K1,K2,K3,…,Kn-1,Kn)调整为大根堆,并利用调整算法写一个建大根堆的算法。

选项

答案void sift(RecType R[],int n){ //把R[n]调成大堆 int j=n;R[0]=R[j]; for(i=n/2;i>=1;i=i/2) if(R[0].key>R[i].key){R[j]=R[i];j=i;} else break; R[j]=R[0]; } void HeapBuilder(RecType R[],int n){ for(i=2;i<=n;i++)sift(R,i); } 提示:此题考查的知识点是堆的插入算法。从第n个记录开始依次与其双亲(n/2)比较,若大于双亲则交换,继而与其双亲的双亲比较,以此类推直到根为止。

解析
转载请注明原文地址:https://kaotiyun.com/show/K3Ci777K
0

最新回复(0)