Question

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

A 79,46,56,38,40,84
B 84,56,79,40,46,38
C 84,79,56,46,40,38
D 84,79,56,38,40,46
是求初始堆~答案是A，不知道怎么做的，拜托高手讲一下~详细些~谢谢~

Answer 1

写一个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/2; i<=1; i++) /*初始建堆，从最右非叶结点开始*/
PushDown( i, n); /*整理堆，把以i为根，最大下标的叶为n*/
for( i=n; i<=2; i--) {
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;

Answer 2

为一个无序序列建立堆的过程就是对完全二叉树从下往上反复"筛选(筛选法调整堆)"的过程。因为完全二叉树的最后一个非叶结点的编号为(n/2)-1,所以"筛选"只需从编号(n/2)-1的结点开始。按照筛选法将完全二叉树调整成满足堆的定义，则得出来的就是初始堆。
所以答案为(84 79 56 38 40 46)，选D。
信不信由你，我是对着数据结构书中建初始堆的过程做出来的

Answer 3

正确答案是C
我们默认关键字是46和84比。大的话。换过来84,79,56,38,40,46
然后就是79跟46比 ，大46，顺序不变
56和46比。顺序也不边
38和46 小。换过来。，现在的记过是84,79,56,46,40,38
然后用40和38比。不变所以答案就是 84,79,56,46,40,38

Answer 4

构造初始结构：(用大顶堆)
46
79 56
38 40 84
从最后一个非叶子结点开始，依次调整：
46
79 84
38 40 56
84
79 46
38 40 56
84
79 56
38 40 46
即84,79,56,38,40,46

Answer 5

额。。堆排序。。这是数据结构的啊。。。不是数据库方面的哦。。呵呵。。大一还是大二上的了差不多忘记了。。。