#include<stdio.h>
#include<conio.h>
int c=0;
void heap_sort(int no[],int ar);
void shift(int no[],int root,int bottom);
int no[10];
void main()
{
int i;
clrscr();
printf("enter any 10 values for heap sort");
for(i=0;i<10;i++)
scanf("%d",&no[i]);
heap_sort(no,10);
printf("after sorting\n\n");
for(i=0;i<10;i++)
printf("%d\t",no[i]);
printf("\nthe complexity of heap sort is =%d",c);
getch();
}
void heap_sort(int no[10],int ar)
{
int i,temp;
for(i=(ar/2);i>=0;i--)
shift(no,i,ar);
for(i=ar-1;i>=1;i--)
{
temp=no[0];
no[0]=no[i];
no[i]=temp;
shift(no,0,i-1);
}
}
void shift(int no[10],int root,int bottom)
{
int d=0,temp,max;
while((root*2<=bottom) && (!d))
{
c++;
if(root*2==bottom)
max=root*2;
else if(no[root*2]>no[root*2+1])
max=root*2;
else
max=root*2+1;

if(no[root]<no[max])
{
temp=no[root];
no[root]=no[max];
no[max]=temp;
root=max;
}
else
d=1;
}

}