#include<cstdlib>
#include<iostream>
using namespace std;
void bulidMaxHeap(int a[]);
void MaxHeapfy(int a[], int i);
void heapSort(int a[]);
int n;
int main ()
{
int i,j,a[100],m;
cout<<"How many number"<<endl;
cin>>n;
cout<<"Enter your number"<<endl;
for(i=0;i<n;i++)
cin>>a[i];
m=n;
n=n-1;
heapSort(a);
cout<<"After sorting the number's"<<endl;
for(i=0;i<m;i++)
cout<<a[i]<<" ";
cout<<endl<<endl;
system("PAUSE");
}
void heapSort(int a[])
{
int i,t;
bulidMaxHeap(a);
for(i=n;i>=1;i--)
{
t=a[0];
a[0]=a[i];
a[i]=t;
n--;
MaxHeapfy(a,0);
}
}
void bulidMaxHeap(int a[])
{
int i;
for(i=(n/2);i>=0;i--)
{
MaxHeapfy(a,i);
}
}
void MaxHeapfy(int a[], int i)
{
int l,r,lr,temp;
l=i*2+1;
r=i*2+2;
if(l<=n && a[l]>a[i])
lr=l;
else
lr=i;
if(r<=n && a[r]>a[lr])
lr=r;
if(lr!=i)
{
temp=a[i];
a[i]=a[lr];
a[lr]=temp;
MaxHeapfy(a,lr);
}
}
#include<iostream>
using namespace std;
void bulidMaxHeap(int a[]);
void MaxHeapfy(int a[], int i);
void heapSort(int a[]);
int n;
int main ()
{
int i,j,a[100],m;
cout<<"How many number"<<endl;
cin>>n;
cout<<"Enter your number"<<endl;
for(i=0;i<n;i++)
cin>>a[i];
m=n;
n=n-1;
heapSort(a);
cout<<"After sorting the number's"<<endl;
for(i=0;i<m;i++)
cout<<a[i]<<" ";
cout<<endl<<endl;
system("PAUSE");
}
void heapSort(int a[])
{
int i,t;
bulidMaxHeap(a);
for(i=n;i>=1;i--)
{
t=a[0];
a[0]=a[i];
a[i]=t;
n--;
MaxHeapfy(a,0);
}
}
void bulidMaxHeap(int a[])
{
int i;
for(i=(n/2);i>=0;i--)
{
MaxHeapfy(a,i);
}
}
void MaxHeapfy(int a[], int i)
{
int l,r,lr,temp;
l=i*2+1;
r=i*2+2;
if(l<=n && a[l]>a[i])
lr=l;
else
lr=i;
if(r<=n && a[r]>a[lr])
lr=r;
if(lr!=i)
{
temp=a[i];
a[i]=a[lr];
a[lr]=temp;
MaxHeapfy(a,lr);
}
}
Output
No comments:
Post a Comment