C++ program to implement Heap sort Algorithm

#include <iostream.h>
const int MAX = 10 ;
class array
{
	private :
		int arr[MAX] ;
		int count ;
	public :
		array( ) ;
		void add ( int num ) ;
		void makeheap(int ) ;
		void heapsort( ) ;
		void display( ) ;
} ;
array :: array( )
{
	count = 0 ;
	for ( int i = 0 ; i < MAX ; i++ )
		arr[MAX] = 0 ;
}
void array :: add ( int num )
{
	if ( count < MAX )
	{
		arr[count] = num ;
		count++ ;
	}
	else
		cout << "\nArray is full" << endl ;
}
void array :: makeheap(int c)
{
 
	for ( int i = 1 ; i < c ; i++ )
	{
		int val = arr[i] ;
		int s = i ;
		int f = ( s - 1 ) / 2 ;
		while ( s > 0 && arr[f] < val )
		{
			arr[s] = arr[f] ;
			s = f ;
			f = ( s - 1 ) / 2 ;
		}
		arr[s] = val ;
	}
}
void array :: heapsort( )
{
	for ( int i = count - 1 ; i > 0 ; i-- )
	{
		int ivalue = arr[i] ;
		arr[i] = arr[0] ;
		arr[0]=ivalue;
		makeheap(i);
 
	}
}
void array :: display( )
{
	for ( int i = 0 ; i < count ; i++ )
		cout << arr[i] << "\t" ;
	cout << endl ;
}
void main( )
{
	array a ;
 
	a.add ( 11 ) ;
	a.add ( 2 ) ;
	a.add ( 9 ) ;
	a.add ( 13 ) ;
	a.add ( 57 ) ;
	a.add ( 25 ) ;
	a.add ( 17 ) ;
	a.add ( 1 ) ;
	a.add ( 90 ) ;
	a.add ( 3  ) ;
	a.makeheap(10) ;
	cout << "\nHeap Sort.\n" ;
	cout << "\nBefore Sorting:\n"  ;
	a.display( ) ;
	a.heapsort( ) ;
	cout << "\nAfter Sorting:\n" ;
	a.display( ) ;
}

14 Responses to “C++ program to implement Heap sort Algorithm”

srihari August 9, 2011

its simple and very interesting .and can u please implement like those codes with user defined variables..
i.e giving input at run time…
srihari August 9, 2011

please write codes only using “for” loops…
shravani reddy November 20, 2011

its easily understandable and i need d pgms of stacks using array and linked lilist and also queues
sunil choudhary January 21, 2012

please give the algorithm using max heap
Navaz August 4, 2012

Ur code is really understandable..plz give the cpp code for sparse matrix addition and transpose
Aristotle Doria October 1, 2012

It’s output is just the same with those in the selection sort. Does the code also works for the selection sort or only for heap sort?
goutham October 8, 2012

please use some meaningfull variable names
shani October 9, 2012

plz write the code 4 heap sort tht takes input data frm the txt file
Andre March 13, 2013

Correct me if I am wrong, instead of

while ( s > 0 && arr[f] 0 && arr[f] < val )
{
arr[s] = arr[f] ;
s = f ;
f = ( s – 1 ) / 2 ;
}
arr[s] = val ;
void array :: makeheap(int c)
{

for ( int i = 1 ; i 0 && arr[f] < val )
{
swap(arr, s, f)
s = f ;
f = ( s – 1 ) / 2 ;
}
}
}
Debabrat June 30, 2013

write a program for priority queue. where all the property will satisfy that means maximum, heap increase key, insertition, deletion , return max operation should present?
nicky October 18, 2014

what is the time complexity is it O(nlogn) or O(n*n). your using two for loops.
Software Engineer January 29, 2015

very bad coding …..
Nitin Kumar March 14, 2015

Better way to implement Heap Sort
ambika February 4, 2017

output doesn,t display plz display