#include<stdio.h>
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a=*b;
*b=temp;
}

void Heapify(int A[],int i,int m)
{
int l,r,max;
    l=2*i+1;
    r=2*i+2;
    max=i;
    if(l<=m && A[l]>A[max])
        max=l;
    if(r<=m && A[r]>A[max])
        max=r;
    if(max!=i)
{
        swap(&A[i], &A[max]);
        Heapify(A,max,m);
}
}

void Heapify2(int A[],int i,int m)
{
int l,r,max;
    max=i;
    while(max<=m)
{
        l=2*max+1;
        r=2*max+2;
        i=max;
        if(l<=m && A[l]>A[i])
            max=l;
        else
            max=i;
        if(r<=m && A[r]>A[max])
            max=r;
        if (i!=max)
            swap (&A[i], &A[max]);
        else
            return;
}
}

void BuildHeap(int n,int A[])
{
    for (int i=n/2; i>=0;i--)
        Heapify(A,i,n);
}

void HeapSort(int n,int A[])
{
int m;
    BuildHeap(n,A);
    m=n;
    while(m>=1)
{
        swap(&A[0], &A[m]);
        m=m-1;
        Heapify(A,0,m);
}
}

void main()
{
int A[]={5,2,4,6,8,1,3};
HeapSort(sizeof(A)/sizeof(int)-1,A);
for(int i=0;i<sizeof(A)/sizeof(int);i++)
printf("%d, ", A[i]);

}