A-A+

已知关键字序列(K1 K2 K3 … Kn-1)是大根堆。试写出一算法将(K1 K2 K3

2022-08-12 16:02:53 问答库阅读 196 次

问题详情

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

请帮忙给出正确答案和分析，谢谢！

参考答案

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