理解过程后,发现如果程序的下标是从0开始,那么树的左孩子是2k+1,右孩子是2k+2,贴上自己的程序,请各位高手看看还有什么错误?
#include <stdio.h>
#include <stdlib.h>
FILE *fin,*fout;
void file_start()
{
if((fin=fopen("hsort.in","r"))==NULL)
{
printf("Cannot open this file!\n");
getchar();
exit(0);
}
if((fout=fopen("hsort.out","w"))==NULL)
{
printf("Cannot open this file!\n");
getchar();
exit(0);
}
}
void sift(int startPos,int endPos,int number[])
{
//startPos是完全二叉树(堆)中,当前要处理的节点编号
//endPos是当前要处理的堆中的元素个数
//number是堆本身
//根据下面主调函数的实参,可以知道,startPos的值应该是长度为endPos的完全二叉树中的最后一个非叶子节点的编号
int k=2*startPos+1,temp;//根据完全二叉树的性质,编号为startPos的节点的左孩子的编号应该是2*startPos+1,那么k就是startPos节点的左孩子节点
temp=number[startPos];//保存当前父亲节点的值,有可能覆盖
while(k<endPos)//如果还有中间节点没有处理完
{
if(k+1<endPos&&number[k]<number[k+1]) k++; //number[k]和number[k+1]分别是number[i]的左、右孩子,这是在找值最大的孩子
if(temp<number[k])//如果孩子比其父节点的值都大的话,则覆盖父节点的值,看来这是要形成“大根堆”
{
number[startPos]=number[k];//覆盖操作
startPos=k;//让节点指针移动到值交换之后的子节点处
k=2*startPos+1;//k依然指向i的左孩子节点
}
else
break;//如果没有交换,即number[i]、number[k]和number[k+1]所构成的堆本身满足大根堆,则不需要再向下继续了
}
number[startPos]=temp;//将函数一开始要移动的number[i]的值,移动到现在(可能移动、也可能没有移动)的number[i]里
}
void heap_sort(int number[],int n)
{
int i,temp=0;
for(i=n/2;i>=0;i--)
sift(i,n,number);
for(i=n-1;i>=0;i--)
{
temp=number[i];
number[i]=number[0];
number[0]=temp;
sift(0,i,number);
}
}
int main()
{
int i,number[10000]={0},n;
file_start();
fscanf(fin,"%d",&n);
for(i=0;i<n;i++)
fscanf(fin,"%d",&number[i]);
heap_sort(number,n);
for(i=0;i<n;i++)
fprintf(fout,"%d ",number[i]);
system("pause");
return 0;
}