DATA STRUCTURES PROGRAMS

ARRAYS-STRUCTURES  POINTERS  LINKED LISTS STACKS  QUEUES  TREES  HASHING HEAPS  GRAPHS  SEARCHING  SORTING

PROGRAM TO IMPLEMENT HEAP SORT USING ARRAYS USING C

#include <stdio.h>
#include <conio.h>
void main()
{
int i,v,p,l[100],n,k,t,j;
clrscr();
printf("enter the number");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&l[i]);
}
printf("\nentered list are as follows");
for(i=1;i<=n;i++)
{
printf("\t%d",l[i]);
}
/*creation of heap*/
for(k=2;k<=n;k++)
{
i=k;
t=l[k];
j=i/2;
while((i>1)&&(t > l[j]))
{
l[i]=l[j];
i=j;
j=i/2;
if(j<1)
j=1;
}
l[i]=t;
}

printf("\nHEAP");

for(i=1;i<=n;i++)
{
printf("\t%d",l[i]);
}
printf("\n");
//heapsort
for(k=n;k>=2;--k)
{
t=l[1];
l[1]=l[k];
l[k]=t;
i=1;
v=l[1];
j=2;
if((j+1)
if(l[j+1]>l[j])
j++;
while((j<=(k-1))&&(l[j]>v))
{
l[i]=l[j];
i=j;
j=2*i;
if((j+1)
if(l[j+1]>l[j])
j++;
else
if(j>n)
j=n;
l[i]=v;
}
for(p=1;p<=n;p++)
{
printf("\t%d",l[p]);
}
printf("\n");
}
printf("\nthe sorted list ");
for(i=1;i<=n;i++)
{
printf("\t%d",l[i]);
}
getch();

}