Heap Sort in CPP

Whats is Heap Sort ?

Heap is a binary tree based data structure. A binary tree has a parent who has two nodes or children at most. A tree is a hierarchy based data structure, you have a certain order in placing the elements.

Who Invented Heap Sort ?

Heapsort was invented by J. W. J. Williams in 1964.

Working

Firstly the un-sorted list and we create a Heap data structure(Max-Heap or Min-Heap). Now you can put the first element of the heap in your array (the first element of the Heap is either largest or smallest(depending upon Max-Heap or Min-Heap)). Again make heap using remaining list data. pick first element and put this into array. This process is repeated until list complete sorted.
Program

//Heap Sort
#include<iostream.h>
#include<conio.h>
//Display function
void display(int array[],int size){
for(int i=0;i<size;i++){
cout<<array[i];
(size==i+1)? cout<<".": cout<<",";
}
}
//Swap Function
void swap(int array[],int left,int right){
//Interchange Two Element in Array
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
//Heapify Function
void Heapify(int input[],int n,int i){
int largest = i;
int l = i + 1;
int r = i + 2;
if (l < n && input[l] > input[largest])
largest = l;
if (r < n && input[r] > input[largest])
largest = r;
if (largest != i){
int left = i;
int right= largest;
swap(input,left,right);
Heapify(input, n, largest);
}
}
//Sort Heap
void SortHeap(int array[],int size){
for (int i = size - 1; i >= 0; i--){
Heapify(array, size, i);
}
for (int j = size - 1; j >= 0; j--){
int left = 0;
int right= j;

swap(array,left,right);
Heapify(array, j, 0);
}
}
//Main Function
void main(){
clrscr(); //Clear Screen
int array[10]={45,65,55,75,12,59,89,49,62,20}; // Array
int size=10; //Size
cout<<"\n ------ Heap Sort ------ ";
cout<<"\nBefore Sorting\n";
display(array,size); //Display Before Sort
SortHeap(array,size); //Heap Sorting
cout<<"\nAfter Sorting\n";
display(array,size); //Display After Sorting
getch();
}

Output