#include<iostream.h>
#include<conio.h>
int count=0;
int co=0;
int cp=0;
void
heap(int[],int);
void
build(int[],int);
void
max(int[],int,int);
void main()
{clrscr();
int n,a[20];
cout<<"enter
the no of elements"<<endl;
cin>>n;
cout<<"enter
the size of array"<<endl;
for(int
i=1;i<=n;i++)
{
cin>>a[i];
}
heap(a,n);
cout<<"sorted
array is"<<endl;
for(i=1;i<=n;i++)
{
cout<<a[i]<<"
";
}
cout<<"no
of comparision "<<count+co;
getch();
}
void
heap(int a[],int n)
{
int temp;
build(a,n);
for(int i=n;i>=2;i--)
{
temp=a[1];
a[1]=a[i];
a[i]=temp;
max(a,1,i-1);
}
}
void build(int a[],int n)
{
for(int i=n/2;i>=1;i--)
{
max(a,i,n);
}
}
void max(int a[],int i,int n)
{
int le,temp;
int l=2*i;
int r=2*i+1;
count++;
if(l<=n&&a[l]>a[i])
{
le=l;
}
else
{
le=i;
}
if(r<=n&&a[r]>a[l])
{ co++;
le=r ;
}
if(le!=i)
{
temp=a[i];
a[i]=a[le];
a[le]=temp;
max(a,le,n);
}
}
Output:-
Comments
Post a Comment