Question

用C语言写的大顶堆排序问题，运行结果不对，请各位大神指教。

#include<stdio.h>
#include<stdlib.h>
void HeapAdjust(int *x,int root,int rear) //筛选程序---root为根结点，rear为最后一个结点
{
if(rear>root)
{
int i,j,k,t;
i=root; //i指向根结点
while(2*i<=rear)
{
j=2*i; //j指向i的左儿子
if(x[j]>=x[j+1]) //选出两个儿子结点的最大值
k=j;
else
k=j+1;
if(x[i]<x[k])
{
t=x[i];
x[i]=x[k];
x[k]=t;
}
i=k;
}
}
}
void CreatHeap(int *x,int rear) //将一棵树建成一个大顶堆，x为存储树的数组，rear为树的最后一个结点
{
int j;
for(j=rear/2;j>=1;j--)
HeapAdjust(x,j,rear);
}
void HeapSort(int *x,int rear)
{
int i,t;
for(i=rear;i>1;i--)
{
t=x[1];
x[1]=x[i];
x[i]=t;
HeapAdjust(x,1,i-1);
}
}
int main()
{
int i;
int R[9]={0,49,38,65,97,76,13,27,49}; //初始堆
CreatHeap(R,8); //建立大顶堆
printf("将初始堆建成大顶堆：");
for(i=1;i<=8;i++)
printf("%d ",R[i]);
printf("\n");
HeapSort(R,8); //堆排序
printf("\n堆排序后为：");
for(i=1;i<=8;i++)
printf("%d ",R[i]);
printf("\n");
return 0;
}

Answer 1

问题出在HeapAdjust上

你只用while(2*i<配神=rear)判断了左儿知仿子存在，都还不知道右儿子存不存在呢就贸然使用x[j+1]，万一不存在呢？轻则出错，重则整个程搭卖纤序因为指针越界而崩溃。

追问

是不是要改成while(2*i<=rear&&2*i+1<=rear)？

追答

不是的，完全有可能只存在左儿子而没有右儿子，若果你那样改的话，这种情况就会被忽略掉。
你应当在while循环里判断右儿子是否存在，若不存在，就只拿当前root跟左儿子比较，若存在，才能按你原来的流程比较三者

追问

如果while(2*i<=rear)不行的话，大顶堆怎么会建好呢。
程序运行结果上，大顶堆可以建成的。

追答

while(2*i=rear) //右儿子不会存在
k=j;
else if(x[j]>=x[j+1]) //右子存在但没有左子大
k=j;
else
k=j+1;
if(x[i]<x[k])
{
t=x[i];
x[i]=x[k];
x[k]=t;
}
i=k;
}
试试吧，我还没调过

已验证，如今结果已经正确了。若有问题，欢迎继续追问