Write a program of Heap sort, it is a type of tree sort and a heap is defined to a binary tree with the key in each node such that all the leaves of the tree are on two adjacent levels. All leaves on lowest level occur to the left and all levels, except possible the lowest are filled.

#include

main()

{

int ar[100],i,n;

void heap(int[],int);

int pqmaxdelete(int[],int);

printf(“\n enter size of array”);

scanf(“%d”,&n);

for(i=0;i<=n-1;i++)

{

printf(“\n enter element”);

scanf(“%d”,&ar[i]);

}

printf(“\n elements before sorting”);

for(i=0;i<=n-1;i++)

scanf(“\n%d”,&ar[i]);

heap(ar,n);

printf(“\n elements after sorting”);

for(i=0;i<=n-1;i++)

scanf(“\n%d”,&ar[i]);

}

void heap(int ar[],int n)

{

int i,ele,c,p,x,j;

for(i=0;i<=n-1;i++)

{

ele=ar[i];

c=i;

p=(c-1)/2;

while(c>0&&ele>ar[p]);

{

ar[c]=ar[p];

c=p;

p=(c-1)/2;

}

ar[c]=ele;

}

for(i=0;i<=n-1;i++)

{

ar[i]=pqmaxdelete(ar,i+1);

}

}

int pqmaxdelete(int ar[],int n)

{

int x,a,ele,j,i=n-1;

x=ar[0];

ar[0]=ar[i];

ele=ar[0];

j=1;

while(j<=i-1)

{

if(j

j++;

if(ele>=ar[j])

break;

ar[(j-1)/2]=ar[j];

j=2*j+1;

}

ar[(j-1)/2]=ele;

return x;

}

Output:

enter size of array5

enter element33

enter element55

enter element11

enter element44

enter element22

elements before sorting

33

55

11

44

22

elements after sorting

11

22

33

44

55