#include
#define N 100
int b[N];//用b[]存放剔出的最大值。
void max_heapify(int *a,int i,int n)//从某结点开始往下进行“堆化简”。
{
int l=2*i+1;
int r=2*i+2;
int largest=0;
if(l<=n&&a[l]>a[i])
largest=l;
else largest=i;
if(r<=n&&a[r]>a[largest])
largest=r;
if(largest!=i)
{
int tmp=a[i];
a[i]=a[largest];
a[largest]=tmp;
max_heapify(a,largest,n);
}
}
void build_maxheap(int *a,int n)//创建最大堆。
{
int i;
for(i=n/2-1;i>=0;i--)
max_heapify(a,i,2*i+2);
}
void heapsort(int *a,int n)//堆排序。
{
build_maxheap(a,n);
int i,j=0;
for(i=n;i>=1;i--)
{
b[j++]=a[0];
int tmp=a[0];
a[0]=a[i];
a[i]=tmp;
n=n-1;
max_heapify(a,0,n);
}
}
int main()
{
int a[]={3,-5,6,2,87,54,23,65,11,98};
int i;
for(i=0;i<10;i++)
printf("%d ",a[i]);
heapsort(a,10);
printf("\n");
for(i=9;i>=0;i--)
printf("%d ",b[i]);
return 0;
}