Question

有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ）

答案是什么？求详细解答 筛选方法是什么? 好纠结 呜呜
选项
a．-1，4，8，9，20，7，15，7 b．-1，7，15，7，4，8，20，9
c．-1，4，7，8，20，15，7，9 d．a，b，c均不对。

Answer 1

如果你的问题是递减排序，就需要首先建立一个小根堆
因为其中有重复的关键字，因此当左右孩子相等并且需要和双亲调整时，原则上无论左右哪一个都可以，所以实际上这个问题会出现两个答案：
-1, 4, 7, 8, 20, 15, 7, 9 和-1, 4, 7, 8, 20, 7, 15, 9
一般算法都是和左子树的调整，这时就是前面的答案了

如果你的问题是递增排序，就需要先建立一个大根堆，不过这时只有唯一的答案：
20, 15, 7, 8, 9, -1, 7, 4

Answer 2

初始序列建立的堆为：
15
9 7
8 20 -1 7
4
由于选项的第一个元素是-1所以我们尝试建小顶堆，因为大顶堆显然不符合任何选项。
第一步：
15
4 -1
8 20 7 7
9
第二步：
-1
4 7
8 20 15 7
9
因此得到的序列为 -1，4，7，8，20，15，7，9

Answer 3

#include <stdio.h>

typedef struct rectype{

int key;

}rectype;

void HEAPSORT(rectype R[],int n);
void SIFT(rectype R[],int i,int m);

void HEAPSORT(rectype R[],int n){

int i;
int j;
rectype temp;

for(i=n/2;i>=1;i--)
SIFT(R,i,n);

for(j=1;j<=n;j++){
printf("%d ",R[j].key);
}

for(i=n;i>=1;i--){

temp = R[1];
R[1] = R[i];
R[i] = temp;

SIFT(R,1,i-1);
}

}

void SIFT(rectype R[],int i,int m){

int j;
rectype temp = R[i];//NOTE

j = i*2;

while(j<=m){

if((j<m)&&(R[j].key > R[j+1].key)) j++;

if(temp.key > R[j].key){

i = j;

j = 2*i;

}
else break;
}
R[i] = temp;

}

int main()
{

int i;
rectype R[9]={0,15,9,7,8,20,-1,7,4};
int n=8;
HEAPSORT(R,n);
return 0;
}