Program for Heap Sort in C++ with Heap sort Algorithm

Heap Trees are binary trees as well as complete Binary Trees . Sorting is a major application of heap trees . Similar to other data Structures Insertion , Deletion and Display operations can be performed in Heap trees . The Timing complexity of Heap tree for insertion , deletion operations is O(logn) . There are 2 types of heap trees :

1. Max Heap Tree

2. Min Heap Tree

Max Heap :

According to Max heap Child nodes should have a value less when compared to parent node element . Simply parent element should have large value than its children . Root node contains the maximum value from the entire tree .

Min Heap :

According to Min Heap child node should contains value more than the parent values . The leaf node contains Max value in the entire tree and root node element has the minimum value from the Heap Tree .

image credits : wikipedia.org

Applications of Heap Tree :

1. Priority Queues which are widely used in the CPU scheduling algorithms in operating systems are generally implemented using Max heaps .

2. Heap sort one of the best sorting techniques is implemented using either Max heap or Min heap trees .

In this tutorial I will be using Max Tree to implement all the operations such as Insertion , Deletion , Sorting . Of course these operations can be implemented using Min heap trees as well .

Also check : Program for Linked list in c++

Insertion in Max Heap Tree :

Insertion operation refers to inserting an element into heap tree . The first element inserted is root node . Other elements are inserted simultaneously . After inserting an element we need to check whether the tree follows the Max heap principle i.e root element should be highest when compared to left and right sub-trees .If it violates the principle the inserted element must be swapped with the root element . 

Deletion in Max heap tree :

Deleting an element from Max heap tree is very simple . The root node must get deleted from the Heap tree .Then after the deleted the root node the tree becomes incomplete and violates the Max heap tree principle . So the root element must be replaced with the most recently inserted element from the heap tree . The most recently inserted element must be deleted .

Also check : Program for Queue Data Structure in c++

Heap sort Algorithm :

Heap sorting is completely based on the deletion of a node from the Max heap tree .

• Construct a Max Heap tree or Min heap tree .
• Remove or delete the root node and copy the element in the root node into a resultant array .
• Reconstruct the Max heap tree or Min heap tree by replacing with most recent inserted element form the Heap tree .
• Repeat the step 2 and step 3 till all the elements are copied into the resultant array and the tree is empty .
• Return resultant array .

Resultant array itself is a sorted array . 

Program for Heap sort using c++ :

#include<iostream.h>
#include<conio.h>
#include<math.h>
class heap
{
public:
    int *a,pos,size,*r,pr;
    public:
heap()
{
int i;
cout<<"\n enter size \n";
cin>>size;
a=new int[size];
r=new int[size];
pos=0;
pr=0;
for(i=0;i<size;i++)
a[i]=-1;
}

void heapsort()
{
while(pos<size)
{
cout<<"\n enter element \n";
cin>>a[pos++];
int k=pos-1;
while(k>0)
{
if(a[k]>a[((int)ceil((k)/2.0))-1])
{
swap(&a[k],&a[((int)ceil((k)/2.0))-1]);
k=((int)ceil((k)/2.0))-1;
}
else
break;
}
}
cout<<"\n position is "<<pos<<"n";
cout<<"\n elements in tree are n";
for(int i=0;i<pos;i++)
cout<<" "<<a[i];
}

void sorting()
{
while(pos!=0)
{
cout<<"\n pos is "<<pos<<" ";
remove();
}
}


void remove()
{
r[pr++]=a[0];
cout<<" element copied is "<<a[0];
a[0]=a[pos-1];
a[pos-1]=-1;
pos--;
int i=0;
while( (a[2*i+1]!=-1) && (a[2*i+2]!=-1) &&  (a[i]<a[2*i+1] || a[i]<a[2*i+2]) )
{
if(a[2*i+1]>a[2*i+2])
{
swap(&a[i],&a[2*i+1]);
i=2*i+1;
}
else
{
swap(&a[i],&a[2*i+2]);
i=2*i+2;
}
}
}

void display()
{
int i;
cout<<"\n Elements after sorting \n";
for(i=0;i<pr;i++)
cout<<"  "<<r[i];
}

void swap(int *x, int *y)
{
int temp;
cout<<"\n swapping elements "<<*x<<"and "<<*y;
temp=*x;
*x=*y;
*y=temp;
}

};

void main()
{
heap k;
clrscr();
k.heapsort();
k.sorting();
k.display();
getch();
}

Also check : Program for Stack Data Structure in c++
The order of worst case timing complexity of Heap sort algorithm is O(nlogn).  If you can implement the code in a better way please comment below . Also share your logic , idea with us through comments .