Saturday 1 August 2015

Heap Sort Program


#include<iostream .h>
#include<conio .h>
int heapsize,length;
void exchange(int &a,int &b)
{
 int temp;
 temp=a;
 a=b;
 b=temp;
}
void maxheapify(int a[],int i)
{
 int l,r,largest,temp;
 l=2*i;               //left[i]
 r=2*i+1;         //right[i]
 if(l<=heapsize&&a[l]>a[i])
  largest=l;
 else
  largest=i;

 if(r<=heapsize&&a[r]>a[largest] )
  largest=r;
 if(largest!=i)
  {
  exchange(a[i],a[largest]);
   maxheapify(a,largest);
  }
}
void buildmaxheap(int a[])
{
 heapsize=length;
 for(int i=length/2;i>=1;i--)
  maxheapify(a,i);
}
void heapsort(int a[])
{
 buildmaxheap(a);
 for(int i=length;i>=2;i--)
 {
  exchange(a[1],a[i])  ;
  heapsize-=1;
  maxheapify(a,1);
 }
}
void main()
{
clrscr();
int *a,n;
cout<<"\nEnter the no of element you want(max 20):";
cin>>n;
length=n;
a=new int[n+1];   //DYNAMICALLY INITIALISE ARRAY,AS ARRAY MUST START FROM INDEX 1 SO SIZE IS (N+1)
cout<<"\nEnter the elements:\n";
for(int i=1;i<=n;i++)
 cin>>a[i];
heapsort(a);
cout<<"\nSorted Array is:\n";
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
getch();
}

No comments:

Post a Comment