已知由n-1个关键字组成的序列(K
1
，K
2
，…，K
n-1
)是大顶堆，现在增加一个关键字K
n
，要求将关键字序列(K
1
，K
2
，…，K
n-1
，K
n
)，重新调整为大顶堆。请完成以下要求：
问答题
给出算法的基本设计思想。
【正确答案】正确答案：基本设计思想：从根结点的父母结点的标号[n／2]开始向上，对每个当前结点和左右子树进行调整。最开始的时候要判断n是左结点还是右结点，之后的情况一定是左右结点都有。每次把当前结点的标号除以2则得到当前结点的父母结点的标号。
【答案解析】
问答题
根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
【正确答案】正确答案：算法实现如下： #define n 100； ／／宏定义n常量，由用户自定义结点个数 int K[n]; ／／关键字序列 void heap() { int i=n／2； ／／找到最后一个结点的父母结点 if(n％2==1) ／／当n是右结点时 { if(K[i]＜K[n=1]＆＆K[n-1]＞K[n])swap(K[n-i]，K[i])；／／swap()实现交换两个元素 if(K[i]＜K[n]＆＆K[n-1]＜K[n]}swap(K(n]，K[i])； } else ／／当n是左结点 { if(K[i]＜K[n])swap(K[n]，K[i])； } i=i／2； while(i＞0) ／／依次向上调整 { if(K[i]＜K[n-1]＆＆K[n-1]＞K[n])swap(K[n-1]，K[i])； if(K[i]＜K[n]＆&K[n-1]＜K[n])swap(K[n]，K[i])； i=i／2； } }
【答案解析】
问答题
说明你所设计算法的时间复杂度。
【正确答案】正确答案：时间复杂度分析：在循环当中，我们可以看出每次都是对结点的父母结点进行调整，因此操作次数正好是树的高度，时间复杂度为O(log
2
n)。
【答案解析】