HEAP SORT

  AIM:
To Write a program to sort the element in ascending order using Heap Sort.


ALGORITHM:
STEP 1: Start the Program
STEP 2: Create an Array of size n
STEP 3: Get the n Elements for sorting
STEP 4: Assign the First value stored in array as temp variable
STEP 5: Compare the next value stored in array with the temp value
STEP 6: If the temp value is greater than next value means Swapping the 
two values.                 
STEP 7: Repeat the step 5 and 6 until the entire element will be sorted
STEP 8: Stop the program Execution


PROGRAM:
#include<iostream.h>
#include<stdlib.h> #include<conio.h>
#define MAX 10
class Heap
{
private:
int arr[MAX];
int n;
public: Heap();
void insert(int num);
void makeheap();
void heapsort();
void display();
};
Heap::Heap()
{
n=0;
for(int i=0;i<MAX;i++)
arr[i]=0;
}
void Heap::insert(int num){
if(n<MAX)
{
arr[n]=num;
n++;
}
else
cout<<"\n Array is Full";
}
void Heap::makeheap()
{
for(int i=1;i<n;i++)
{
int val=arr[i];
int j=i;
int f=(j-1)/2;
while(j>0&&arr[f]<val)
{
arr[j]=arr[f];
j=f;
f=(j-1)/2;
}
arr[j]=val;
}
}
void Heap::heapsort(){
for(int i=n-1;i>0;i--)
{
int temp=arr[i];
arr[i]=arr[0];
int k=0;
int j;
if(i==1)
j=-1;
else j=1;
if(i>2&&arr[2]>arr[1])
j=2;
while(j>=0&& temp<arr[j])
{
arr[k]=arr[j];
k=j;
j=2*k+1;
if(j+1<=i-1&&arr[j]<arr[j+1])
j++;
if(j>i-1)
j=-1;
}
arr[k]=temp;
}
}
void Heap::display(){
for(int i=0;i<n;i++) cout<<"\n"<<arr[i];
cout<<"\n";
}
void main()
{
Heap obj;
obj.insert(14); obj.insert(12);
obj.insert(9); obj.insert(8); obj.insert(7);
obj.insert(10); obj.insert(18);
cout<<"\n The elements are..."<<endl;
obj.display();
obj.makeheap();
cout<<"\n Heapified"<<endl;
obj.display();
obj.heapsort();
cout<<"\n elements sorted by heap sort..."<<endl;

obj.display();
getch();
}
OUTPUT: 

The Elements are …  14  12  9 
Heapified  8 7  10  18 
18  12  14  8 7 9 10 
Elements sorted by Heap Sort … 
7 8 9 10  12  14  18