问答题
填空并回答相关问题。
(1)下面是将任意序列调整为最大堆(MAXHEAP)的算法,请将空白部分填上。将任意序列调整为最大堆通过不断调用adjust函数,即
for(i=n/2;i>0;i一一)adjust(1ist,i,n);
其中list为待调整序列所在数组(从下标1开始),n为序列元素个数,adjust函数为:
void adjust(int 1ist[],int root,int n)
/*将以root为下标的对应元素作为待调整堆的根,待调整元素放在list数组中,最大元素下标为n*/
{int child,rootkey;
rootkey=list[root];
child=2*root;
while(chiId<=n)
{ if(child1i8t[child])
break;
else{List[②]=list[child];
child*=2:
}
}
list[child/2]:r00tkey;
}
(2)判断下列序列能否构成最大堆:(12,70,33,65,24,56,48,92,86,33);若不能,按上述算法将其调整为堆,调整后的结果_______________为。【浙江大学1998七(11分)】
【正确答案】正确答案:(1)①child=child+1;②child/2 (2)原序列不能构成大堆。调整后的大堆是:92,86,56,70,33,33,48,65,12,24
【答案解析】