C++ Program to Perform Heap Sort

Heap Sort

AIM:

• To Write a C++ Program to perform heap sort.

Algorithm:

Step I: The user inputs the size of the heap(within a specified limit).The program generates a corresponding binary tree with nodes having randomly generated key Values.

Step II: Build Heap Operation

Step III: Remove maximum element:The program removes the largest element of the heap(the root) by swapping it with the last element.

Step IV: The program executes Heapify(new root) so that the resulting tree satisfies the heap property.

Step V: Goto step III till heap is empty

Program:

#include<iostream.h>

#include<stdlib.h>

class sorting

{

private:

int n,size;

double *minheap;

public:

void insert_minheap(double);

double delete_one_minheap();

void input();

void output();

};

void sorting::insert_minheap(double n)

{

if(size>=9)

{

cout<<”array overflow “;

exit(0);

}

minheap[++size]=n;

//Reorder the heap

int k=size;

while(k>1) //k has a parent

{

if(minheap[k]<minheap[k/2])

{

double t=minheap[k];

minheap[k]=minheap[k/2];

minheap[k/2]=t;

k/=2;

}

else

break;

}

}

double sorting::delete_one_minheap()

{

if(size<1)

return -1;

double val;

val=minheap[1];

minheap[1]=minheap[size];

size–;

//Reorder the heap by moving down

int k=1;

int newk;

while(2*k<=size) //k has atleast one chaild

{

//Set newk to the index of the smallest chaild of k

if(2*k==size) //if k has only left chaid

{

newk=2*k;

}

else //k has two chailds

{

if(minheap[2*k]<minheap[2*k+1])

newk=2*k;

else

newk=2*k+1;

}

if(minheap[k]<minheap[newk])

break;

else

{

double t;

t=minheap[k];

minheap[k]=minheap[newk];

minheap[newk]=t;

k=newk;

}

}

return val;

}

void sorting::input()

{

cout<<”Enter how many numbers you are going to enter for sorting :”;

cin>>n;

minheap=new double[n+1];

/********** Construct a heap with the input elements *******/

size=0;

cout<<”Now enter the elements\n”;

double number;

for(int i=1;i<=n;i++)

{

cin>>number;

insert_minheap(number);

}

}

void sorting::output()

{

cout<<”The sorted numbers are ::\n”;

for(int i=1;i<=n;i++)

cout<<delete_one_minheap()<<’\t’;

cout<<endl;

}

int main()

{

clrscr();

sorting obj;

obj.input();

obj.output();

getch();

}

Output:

Enter how many numbers you are going to enter for sorting :5

Now enter the elements

9

1

8

2

6

The sorted numbers are:

1 2 6 8 9

Result:

• Thus, the heap sort program has been written and executed successfully.