Concept:Heap is a special case of balanced binary tree data structure where the root-node key is compared with its children and arranged accordingly. If A has child node B then key(A) >= key(B)
As the value of parent is greater than that of child, this property generates Max Heap. Based on these criteria, a heap can be of two types.
Min-Heap − Where the value of the root node is less than or equal to either of its children.
Max-Heap − Where the value of the root node is greater than or equal to either of its children.
ALGORITHM:
1. Get the size of the array from the input.
2. Enter the elements to be sorted.
3. Build a heap.
4. Sort the heap in ascending order.
5. Now the array is contained with sorted elements.
6. Display the sorted elements.
#include <iostream.h>
#include <conio.h>
void main()
{
clrscr();
int a[50],size;
int p,c;
cout<<"Enter the Size of an Array :";
cin>>size;
cout<<"Enter Value of A[1] :";
cin>>a[1];
for(int i=2;i<=size;i++)
{
cout<<"Enter Value of A["<<i<<"] :";
cin>>a[i];
p=i/2;
c=i;
while(1)
{
if( a[c] > a[p])
{
int t=a[c];
a[c]=a[p];
a[p]=t;
}
c=p;
p=p/2;
if(p<1)
{
break;
}
}
}
cout<<endl<<"Heap ..."<<endl;
for(i=1;i<=size;i++)
{
cout<<endl;
cout<<"Arr["<<i<<"] :"<<a[i];
}
int j=size;
int lc,rc;
while(j>1)
{
if(a[1] > a[j])
{
int t=a[1];
a[1]=a[j];
a[j]=t;
j--;
}
else
{
j--;
continue;
}
p=1;
while(p < j)
{
lc=p*2;
rc=p*2 + 1;
if(lc>=j || rc >=j)
{
break;
}
if(a[p] < a[lc] && a[lc] > a[rc])
{
int temp=a[lc];
a[lc]=a[p];
a[p]=temp;
p=lc;
}
else
if (a[p] < a[rc] && a[rc] > a[lc])
{
int temp=a[rc];
a[rc]=a[p];
a[p]=temp;
p=rc;
}
else
{
break;
}
}
}
cout<<endl<<"\nSorted List ..."<<endl;
for(i=1;i<=size;i++)
{
cout<<endl;
cout<<"Arr["<<i<<"] :"<<a[i];
}
getch();
}
