// program to implement Heap sort
#include<iostream.h>
#include<iomanip.h>
#include<conio.h>
class heapsort
{
private:
int *x;
int items;
public:
heapsort(int);
~heapsort();
void input(int []);
void heap_property(int,int);
void construct_heap();
void display();
void sort(int []);
};
heapsort::heapsort(int n)
{
items=n;
x=new int[items+1];
}
heapsort::~heapsort()
{
delete [] x;
}
void heapsort::input(int a[])
{
for(int i=0;i<=items;i++)
x[i]=a[i-1];
}
void heapsort::display()
{
cout<<"\n Sorted elements are :";
for(int i=1;i<=items;i++)
cout<<setw(5)<<x[i];
}
void heapsort::construct_heap()
{
for(int i=items/2;i>0;i--)
heap_property(i,items);
}
void heapsort::heap_property(int root, int limit)
{
int done=0;
int big=x[root];
int j=2*root;
while((j<=limit) && (done==0))
{
if((j<limit) && (x[j]<x[j+1]))
j++;
if(big >=x[j])
done=1;
else
{
x[j/2]=x[j];
j=2*j;
}
}
x[j/2]=big;
}
void heapsort::sort(int a[])
{
construct_heap();
for(int i=(items-1);i>0;i--)
{
int temp;
temp=x[i+1];
x[i+1]=x[1];
x[1]=temp;
a[i]=x[i+1];
heap_property(1,i);
}
a[0]=x[1];
}
int main()
{
int elements[100],n;
clrscr();
cout<<"Enter how many elements \n";
cin>>n;
cout<<"Enter"<<n<<"elements \n";
for(int i=0;i<n;i++)
cin>>elements[i];
heapsort obj(n);
obj.input(elements);
obj.sort(elements);
obj.display();
return 0;
}
Test data
Enter how many elements
8
Enter 8 elements
12 3 45 6 32 21 11 17
Output
Sorted elements are : 3 6 11 12 17 21 32 45