/*

Implement Heap sort by costructing max or min Heap

*/


#include<iostream>

using namespace std;

class Heap
{
int H[25], No;
 public:

Heap()
{
No=0;
}

void create();
void sort();
void display();
};

void Heap::display()
{
cout<<endl;
for(int k=2;k<=No;k++)
cout<<" "<<H[k];
cout<<endl;
}

void Heap::create()
{
int temp,loc;
char ans;
do
{
cout<<"Enter the value";
cin>>H[++No];
loc=No;
while(H[loc]>H[loc/2] && loc>1)
{
temp=H[loc];
H[loc]=H[loc/2];
H[loc/2]=temp;
loc=loc/2;
}
display();
cout<<"Add more(y/n)";
cin>>ans;
}while(ans=='y' || ans=='Y');
}

void Heap::sort()
{
int loc,temp,Pos=No;
do
{
cout<<"\nDELETED ROOT:"<<H[1];
temp=H[1];
H[1]=H[Pos];
H[Pos]=temp;
loc=1;
do
{
if(H[loc]<H[2*loc] && H[2*loc]>H[2*loc+1] && (2*loc)<Pos)
{
temp=H[loc];
H[loc]=H[2*loc];
H[2*loc]=temp;
loc=2*loc;
}
else
if(H[loc]<H[2*loc+1] && H[2*loc]<H[2<loc+1] && (2*loc+1)<Pos)
{
temp=H[loc];
H[loc]=H[2*loc+1];
H[2*loc+1]=temp;
loc=2*loc+1;
}
else
break;
}while(1);
Pos--;
//display();
}while(Pos>1);
cout<<"\n";
display();
}

int main()
{
Heap H;
H.create();
H.sort();
return 0;
}

//END OF PROGRAM