C++ program to implement Heap Sort

#include<iostream>
using namespace std;
void heapsort(int *a,int n);

void adjust(int *a,int root,int n);

 

int main( )

{

    int *a,n;

    cout<<"Enter how many elements :";

    cin>>n;

    a=new int[n+1];

    for(int i=1;i<=n;i++)

    cin>>a[i];

    heapsort(a,n);

    for(i=1;i<=n;i++)

    cout<<a[i]<<" ";

    return 0;

}

 

 

void heapsort(int *a,int n)

{

    for(int i=n/2;i>=1;i--)

    adjust(a,i,n);

    for(i=n-1;i>=1;i--)

    {

       int t=a[i+1];

       a[i+1]=a[1];

       a[1]=t;

       adjust(a,1,i);

    }

}

void adjust(int *a, int root,int n)

{

    int e=a[root];

    int k=e;

    for(int j=2*root;j<=n;j*=2)

    {

             if(j<n)

                if(a[j]<a[j+1])

                j++;

                if(k>=a[j])

                break;

                a[j/2]=a[j];

    }

    a[j/2]=e;

}

Input

Enter how many elements : 9

9   7  5   6  1  8   2  3  4

Output

1  2  3  4  5  6  7  8  9

Leave a Reply

Your email address will not be published.