C or C++ Program for Heap Sort

C or C++ Program for Heap Sort
Heap Sort in C or C++

Heap Sort
Heap sort is a sorting technique based comparison.  It was invented by J. W. J. Williams in 1964. It is part of the selection sort. It is the improvement of basic selection sort and uses a logarithmic time priority queue rather than a linear time search. It takes O (n log n) times.
We can divide the heap sort algorithm into two parts.
In the first parts a heap is built out of the data. The heap is an array with the layout of a complete binary tree.
In the second parts a sorted array is created by repeatedly removing the largest element from the heap (the root of the heap) and inserting it into the array. After each removal the heap is updated to maintain the heap. When all objects have been removed from the heap we get the result which is a sorted array.

Heap Sort Program

#include
#include
class node {
int a[100],n,i;
int heap_size;
public:
     void get_data();
     void max_heapify(int);
     void build_max_heap();
     void heap_sort();
     void show_data();
     } tap;
    void node::get_data(){
cout<<"                    This is a heap short program\n\n\n";
cout<<"How many number you want to enter :"; cin>>n;
cout<<"Enter the values :\n";
for(int i=1;i<=n;i++) cin>>a[i];
heap_size=n;
}

void node::show_data()
{
cout<<"Your sorted data are :\n\n";
for(int i=1;i<=n;i++)
cout<<"\t"<<a[i];
}

void node::max_heapify(int i)
    {
	int l=2*i;
	int r=2*i+1;
	int largest,h;
	    if((l<=heap_size)&&(a[l]>a[i]))
	    largest=l;
	    else
	    largest=i;
	    if((r<=heap_size)&&(a[r]>a[largest]))
	    largest=r;
	   if(largest!=i)
	   {
	   h=a[i];
	   a[i]=a[largest];
	   a[largest]=h;
	   max_heapify(largest);
	   }
	}

void node::build_max_heap()
	{
	heap_size=n;
	for(int i=n/2;i>=1;i--)
	max_heapify(i);
	}

void node::heap_sort()
	{
	build_max_heap();
	int h;
	for(int i=n;i>=2;i=i-1)
	{
	  h=a[1];
	  a[1]=a[i];
	  a[i]=h;
	  heap_size=heap_size-1;
	  max_heapify(1);
	}
	}

void main()
{
clrscr();
tap.get_data();
tap.heap_sort();
tap.show_data();
getch();
}