#include<stdio.h>
#include<math.h>
int h,arr_size;
void maxheap_property(int a[],int i)
{
int l,r,largest,temp;
l=2*i+1; r=2*i+2;
if(l<h && a[l]>a[i]) largest=l;
else largest=i;
if(r<h && a[r]>a[largest]) largest=r;
if(largest!=i)
{
temp=a[i];
a[i]=a[largest];
a[largest]=temp;
maxheap_property(a,largest);
}
}
void build_maxheap(int a[])
{
int i,j;
h=arr_size;
j=floor((arr_size/2));
for(i=j-1;i>=0;i--)
maxheap_property(a,i);
}
void heap_sort(int a[])
{
int i,temp;
build_maxheap(a);
for(i=arr_size-1;i>=1;i--)
{
temp=a[0];
a[0]=a[i];
a[i]=temp; h--;
maxheap_property(a,0);
}
}
int main()
{
int i,n,a[50];
printf("How many numbers: ");
while(scanf("%d",&n) == 1)
{
arr_size=n;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
heap_sort(a);
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
return 0;
}
No comments:
Post a Comment