PROGRAM TO IMPLEMENT HEAP SORT | Data Structures Tutorial pdf

/* PROGRAM TO IMPLEMENT HEAP SORT*/

#include<stdio.h>
int m;
void heap_sort(int *);
void create_heap(int *);
void display(int *);

/* Function to create heap */
void create_heap(int a[])
{
int k,j,i,temp;
for(k=2; k<=m; k++)
{
i = k ;
temp = a[k];
j = i/2 ;
while((i > 1) && (temp > a[j]))
{
a[i] = a[j];
i = j ;
j = i/2;
if ( j < 1 )
{ j = 1; }
}
a[i] = temp;
}
}

/* Function to sort heap */
void heap_sort(int a[])
{
int i,j,k,temp,val;
for(k=m; k>=2; k--)
{
temp = a[1];
a[1] = a[k];
a[k] = temp;
i = 1;
val = a[1];
j = 2 ;
if((j+1) < k)
{
if(a[j+1] > a[j])
{ j++; }
}
while((j <= (k-1)) && (a[j] > val))
{
a[i] = a[j];
i = j;
j = 2*i;
if((j+1) < k)
{ if(a[j+1] > a[j])
{
j++;
}
else if( j > m)
{
j = m;
}
}
a[i] = val;
}
}
}

/* Function to display list */
void display(int a[])
{
int i;
for(i=1; i<=m; i++)
printf("\n\n\t\ta[%d] = %d",i,a[i]);
}

/* Main Function */
void main()
{ int a[20];
int i;
clrscr();
printf("\n\n How many elements you want to insert: ");
scanf("%d",&m);
printf("\n\nEnter the elements:");
for (i=1; i<=m; i++)
{
printf("\n a[%d]= ",i);
scanf("%d",&a[i]);
}
printf("\n\n\t ------------\n\t The list is:\n\t ------------");
display(a);
create_heap(a);
printf("\n\n\t ------------\n\t The heap is:\n\t ------------");
display(a);
heap_sort(a);
printf("\n\n\t -----------------------\n\t The list after sorting:\n\t -----------------------\n");
display(a);
getch();
}