Sunday 6 October 2013

Heap Sort Program in C++

#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;
}
    
     
     

No comments:

Post a Comment