问答题
已知由n一1个关键字组成的序列(K
1
,K
2
,K
3
…K
n-1
)是大顶堆，现在再增加一个关键字K
n
，要求将关键字序列(K
1
,K
2
,K
3
,…，K
n-1
，K
n
)重新调整为大顶堆。请完成以下要求：
(1)编写满足上述要求的算法。
(2)简述你所编写的算法的基本思想。
(3)分析你所编写的算法的时间复杂度。
【南京航空航天大学2006 7(5分)】【江苏大学2006四、1(12分)】
【正确答案】正确答案：(1)因为前n一1个元素已经是堆，所以从第n个记录开始依次与其双亲(n／2)比较，若大于双亲则交换，继而与其双亲的双亲比较，直至满足堆的定义(最多类推到根)。核心语句段如下： j=n；R[0]=R[j]； for(i=n／2；i>=1ji=i12) if(R[0]．key>R[i]．key){R[j]=R[i]; j=i;} else break； R[j]=R[0]; (2)void HeapBuilder(RecType R[]，int n) {for(i=2；i<=n；i++)sift(R，i)；}
【答案解析】