一个堆排序,运行出错,帮忙检查一下,谢谢
]#include <conio.h>
#include <iostream.h>
int PARENT(int i)
{
return i/2;
}
int LEFT(int i)
{
return 2*i;
}
int RIGHT(int i)
{
return 2*i+1;
}
void MAX_HEAPIFY(int *A,int i,int heap_size) //调整堆节点
{
int largest=i;
int temp;
int l=LEFT(i);
int r=RIGHT(i);
if(i<=heap_size&&A[l]>A[i])
largest=l;
if(i<=heap_size&&A[r]>A[i])
largest=r;
if(largest!=i)
{
temp=A[i];
A[i]=A[largest];
A[largest]=temp;
MAX_HEAPIFY(A,largest,heap_size);
}
}
void BUILD_MAX_HEAP(int *A,int heap_size) //建堆
{
int i;
for(i=heap_size/2;i>=1;i--)
MAX_HEAPIFY(A,i,heap_size);
}
void HEAPSORT(int *A,int heap_size) //堆排序
{
int i;
BUILD_MAX_HEAP(A,heap_size);
int temp;
for(i=heap_size;i>=1;i--)
{
temp=A[1];
A[1]=A[i];
A[i]=temp;
MAX_HEAPIFY(A,1,heap_size);
}
}
int main()
{
int a[100];
int size;
while(scanf("%d",&size)==1&&size>0)
{
int i;
for(i=1;i<=size;i++)
cin>>a[i];
HEAPSORT(a,size);
for(i=1;i<=size;i++)
cout<<a[i]<<" ";
cout<<endl;
}
return 0;
}
//运行环境:VC6
结果有错误,帮忙检查一下
[解决办法]
void MAX_HEAPIFY(int *A,int i,int heap_size) //调整堆节点
这个一遍大顶堆得函数逻辑有问题
你每次只对三个点进行了
实际上你应该对从这个点开始的这颗树（以这个点为根的一颗子树）进行建立大顶堆
