#include<iostream>
using namespace std;
#include<conio.h>
template<class T>
void heapsort(T a[],int n)
{
int x;
for(int i=1;i<=n;i++)
{
insert(a,i);
}
for(int i=n;i>=1;i--)
{
delmax(a,i,x);
a[i]=x;
}
}
template<class T>
int insert(T a[],int n)
{
int i=n;
int item=a[n];
while((i>1)&&(a[i/2]<item))
{
a[i]=a[i/2];
i=i/2;
}
a[i]=item;
return 1;
}
template<class T>
int delmax(T a[],int n,int &x)
{
if(n==0)
{
cout<<"heap is empty:";
return 0;
}
x=a[1];
a[1]=a[n];
adjust(a,1,n-1);
return 1;
}
template<class T>
void adjust(T a[],int i,int n)
{
int j=2*i;
int item=a[i];
while(j<=n)
{
if((j<n)&&(a[j]<a[j+1]))
{
j++;
}
if(item>a[j])
{
break;
}
a[j/2]=a[j];
j=2*j;
}
a[j/2]=item;
}
int main()
{
int a[20],n;
cout<<"\nenter the value :";
cin>>n;
cout<<"\n enter the elements:";
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cout<<"\nbefore sorting:";
for(int i=1;i<=n;i++)
{
cout<<a[i]<<"\t";
}
heapsort(a,n);
cout<<"\n";
cout<<"\n elements after sorting:";
for(int i=1;i<=n;i++)
{
cout<<a[i]<<"\t";
}
_getch();
return 0;
}
using namespace std;
#include<conio.h>
template<class T>
void heapsort(T a[],int n)
{
int x;
for(int i=1;i<=n;i++)
{
insert(a,i);
}
for(int i=n;i>=1;i--)
{
delmax(a,i,x);
a[i]=x;
}
}
template<class T>
int insert(T a[],int n)
{
int i=n;
int item=a[n];
while((i>1)&&(a[i/2]<item))
{
a[i]=a[i/2];
i=i/2;
}
a[i]=item;
return 1;
}
template<class T>
int delmax(T a[],int n,int &x)
{
if(n==0)
{
cout<<"heap is empty:";
return 0;
}
x=a[1];
a[1]=a[n];
adjust(a,1,n-1);
return 1;
}
template<class T>
void adjust(T a[],int i,int n)
{
int j=2*i;
int item=a[i];
while(j<=n)
{
if((j<n)&&(a[j]<a[j+1]))
{
j++;
}
if(item>a[j])
{
break;
}
a[j/2]=a[j];
j=2*j;
}
a[j/2]=item;
}
int main()
{
int a[20],n;
cout<<"\nenter the value :";
cin>>n;
cout<<"\n enter the elements:";
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cout<<"\nbefore sorting:";
for(int i=1;i<=n;i++)
{
cout<<a[i]<<"\t";
}
heapsort(a,n);
cout<<"\n";
cout<<"\n elements after sorting:";
for(int i=1;i<=n;i++)
{
cout<<a[i]<<"\t";
}
_getch();
return 0;
}
No comments:
Post a Comment