/* Program of sorting through heapsort*/
# include <stdio.h>int arr[20],n;
main()
{
int i;
printf("Enter number of elements : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr[i]);
}
printf("Entered list is :\n");
display();
create_heap();
printf("Heap is :\n");
display();
heap_sort();
printf("Sorted list is :\n");
display();
}/*End of main()*/
display()
{ int i;
for(i=0;i<n;i++)
printf("%d ",arr[i]);
printf("\n");
}/*End of display()*/
create_heap()
{
int i;
for(i=0;i<n;i++)
insert(arr[i],i);
}/*End of create_heap()*/
insert(int num,int loc)
{
int par;
while(loc>0)
{
par=(loc-1)/2;
if(num<=arr[par])
{
arr[loc]=num;
return;
}
arr[loc]=arr[par];
loc=par;
}/*End of while*/
arr[0]=num;
}/*End of insert()*/
heap_sort()
{
int last;
for(last=n-1; last>0; last--)
del_root(last);
}/*End of del_root*/
del_root(int last)
{
int left,right,i,temp;
i=0; /*Since every time we have to replace root with last*/
/*Exchange last element with the root */
temp=arr[i];
arr[i]=arr[last];
arr[last]=temp;
left=2*i+1; /*left child of root*/
right=2*i+2;/*right child of root*/
while( right < last)
{
if( arr[i]>=arr[left] && arr[i]>=arr[right] )
return;
if( arr[right]<=arr[left] )
{
temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
i=left;
}
else
{
temp=arr[i];
arr[i]=arr[right];
arr[right]=temp;
i=right;
}
left=2*i+1;
right=2*i+2;
}/*End of while*/
if( left==last-1 && arr[i]<arr[left] )/*right==last*/
{
temp=arr[i];
arr[i]=arr[left];
arr[left]=temp;
}
}/*End of del_root*/
