/*
HEAP SORT
ROLL NO:- 09BCE006
*/
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
void create_heap(int n);
void heap_sort(int n);
int k[100];
void main()
{
int n;
clrscr();
cout<<"Enter the no of elements which you want to sort :: ";
cin>>n;
cout<<"Enter the elements "<<endl;
for(int i=1;i<=n;i++)
{
cin>>k[i];
}
heap_sort(n);
cout<<"The sorted list is as follows "<<endl;
for(int j=1;j<=n;j++)
{
cout<<endl<<k[j]<<endl;
}
getch();
}
void heap_sort(int n)
{
int temp,i,j,key;
create_heap(n);
// cout<<"\tTraversal\t\t"<<endl<<endl;
for(int q=n;q>=2;q--)
{
temp=k[1];
k[1]=k[q];
k[q]=temp;
i=1;
key=k[1];
j=2;
if((j+1)<q)
{
if(k[j+1]>k[j])
j++;
}
while(j<=q-1&&k[j]>key)
{
k[i]=k[j];
i=j;
j=2*i;
if((j+1)<q)
{
if(k[j+1]>k[j])
j++;
else if(j>n)
j=n;
}
k[i]=key;
}
/* for(i=1;i<=n;i++)
{
cout<<k[i]<<" ";
}
cout<<endl;*/
}
return;
}
void create_heap(int n)
{
int i,j,key,temp;
for(int q=2;q<=n;q++)
{
i=q;
key=k[q];
j=i/2;
while(i>1&&key>k[j])
{
temp=k[i];
k[i]=k[j];
k[j]=temp;
i=j;
j=i/2;
if(j<i)
j=1;
}
k[i]=key;
}
return;
}
/* OUTPUT ::
Enter the no of elements which you want to sort :: 7
Enter the elements
12
23
35
62
48
49
9
Traversal
49 48 23 12 35 9 62
48 12 23 9 35 49 62
35 12 23 9 48 49 62
23 12 9 35 48 49 62
12 9 23 35 48 49 62
9 12 23 35 48 49 62
The sorted list is as follows
9
12
23
35
48
49
62
*/
Posts
