#include <stdio.h>
void heap_sort(int [],int);
void build_max_heap(int[],int);
void max_heapify(int[],int,int);
void main()
{
    int i,r,hepsize,n;
    int a[50];
    printf("Enter number of elements in array");
    scanf("%d",&n);
    for (i=0;i<n;i++)
    {
        printf("Enter value")
        scanf("%d",&a[i]);
    }
    heapsize=n-1;
    heap_sort(a,heapsize);
    for (i=0;i<n;i++)
    {
        printf("%d",a[i]);
    }
    return;
}
void heap_sort(int a[],int heapsize)
{
    int i ,tmp;
    build_max_heap(a,heapsize);
    for (i=heapsize; i>0;i--)
    {
        tmp=a[i];
        a[i]=a[0];
        a[0]=tmp;
        heapsize--;
        max_heapify(a,0,heapsize);
    }
    }
    void build_max_heap(int a[],int heapsize)
    {
        int i;
        for(i=heapsize/2;i>=0;i--)
        {
            max_heapify(a,i,heapsize);
        }
    }
    void max_heapify(int a[],int i,int heapsize)
    {
        int tmp,largest;
        int l=(2*i)+1;
        int r=(2*i)+2;
        if((l<=heapsize)&&(a[l]>a[i]))
        largest=1;
        else
        largest=i;
        if((r<=heapsize)&&(a[r]>a[largest]))
        largest=r;
        if(largest!=i)
        {
            tmp=a[i];
        a[i]=a[largest];
        a[largest]]=tmp;
        max_heapify(a,largest,heapsize);
        }
    }