对一组记录的关键码为（46,79,56,38,40,84），如果采用堆排序方法，则建立的初始堆是？

写一个pushdown和heapsort函数，按照建立完全二叉树的思想，建立最大堆时，结点值必须大于其左右儿子的值，以堆（的数量）不断扩大的方式进行初始建堆。以堆的规模逐渐缩小的方式进行堆排序。

把待排序的记录序列用完全二叉树的数组存储结构A表示

初始建堆：把数组所对应的完全二叉树以堆不断扩大的方式整理成堆。令i= n/2,…,2,1并分别把以n/2 ,…,2,1 为根的完全二叉树整理成堆，即执行算法PushDown ( i , n )。

堆排序：令i = n, n-1 ,…, 2

1.交换：把堆顶元素(当前最小的)与位置i(当前最大的叶结点下标)的元素交换，即执行swap(A[1],A[i])；

2.整理:把剩余的i-1个元素整理成堆，即执行PushDown(1 , i-1)；

3.重复执行完这一过程之后，则A[1],A[2],…,A[n]是按关键字不增顺序的有序序列。

void HeapSort ( int n , LIST A )

{inti

for( i=n/2i<=1i++) /*初始建堆，从最右非叶结点开始*/

PushDown( i, n)/*整理堆，把以i为根，最大下标的叶为n*/

for( i=ni<=2i--) {

swap(A[1],A[i])//堆顶与当前堆中的下标最大的叶结点交换

PushDown( 1, i-1 )

/*整理堆把以1为根，最大叶下标为i-1的完全二元树整理成堆*/

整理堆算法：PushDown( first , last)

把以A[first]为根，以A[last]为最右边叶结点的完全二叉树整理成堆。根据堆的定义，它要完成的功能是，把完全二元树中的关键字最小的元素放到堆顶，而把原堆顶元素下 推到适当的位置，使(A[first],…,A[last])成为堆。

那么，怎样把关键字最小的元素放到堆顶，把堆顶元素下推到适当位置呢？

具体 *** 作(要点)如下：

把完全二元树的根或者子树的根与其左、右儿子比较如果它比其左／右儿子大，则与其中较小者交换（若、右儿子相等，则与其左儿子交换）。重复上述过程直到以A[ first]为根的完全二元树是堆为止。

PushDown( first , last)算法实现如下：

void PushDown(int first,int last)

{ /*整理堆:A是外部数组,把A[first]下推到完全二元树的适当位置*/

int r=first/* r是被下推到的适当位置，初始值为根first*/

while(r<=last/2) /* A[r]不是叶，否则是堆*/

if((r==last/2) &&(last%2==0)) {/* r有一个儿子在2*r上且为左儿子*/

if(A[r].key>A[2*r].key)

swap(A[r],A[2*r])/*下推*/

r=last/*A[r].key小于等于A[2*r].key或者"大于"，交换后到叶，循环结束*/

} else if((A[r].key>A[2*r].key)&&(A[2*r].key<=A[2*r+1].key)) {

/*根大于左儿子，且左儿子小于或等于右儿子*/

swap(A[r],A[2*r])/*与左儿子交换*/

r=2*r/*下推到的位置也是下次考虑的根*/

} else if((A[r].key>A[2*r+1].key)&&(A[2*r+1].key<A[2*r].key)) {

/*根大于右儿子，且右儿子小于左儿子*/

swap(A[r],A[2*r+1])/*与右儿子交换*/

r=2*r+1/*下推到的位置也是下次考虑的根*/

}else /*A[r]符合堆的定义，不必整理，循环结束*/

r=last

选B

用大根堆排序的基本思想

① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区

② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key

③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。

……

直到无序区只有一个元素为止。

---