#include"iostream"

#include"iomanip"

using namespace std;

void FixHeap(int list[],int root,int key,int bound){

int i,vacant,largerChild;

vacant=root;

while(2*vacant<=bound){

largerChild=2*vacant;

if(largerChild<bound&&list[largerChild+1]>list[largerChild])

largerChild=largerChild+1;

if(key>list[largerChild])

break;

else{

list[vacant]=list[largerChild];

vacant=largerChild;

}//else

}//while

list[vacant]=key;

cout<<"The new list is:\n";

for(i=1;i<=100;i++){//output the list

cout<<setw(2)<<list[i]<<" ";

if(i%10==0)

cout<<"\n";

}//for

}//FixHeap

void HeapSort(int List[],int N){

int i,max;

for(i=N/2;i>=1;i--)

FixHeap(List,i,List[i],N);

for(i=N;i>=2;i--){

max=List[1];

FixHeap(List,1,List[i],i-1);

List[i]=max;

}//for

}//HeapSort

int main(){

int a[101],i;

a[0]=0;

for(i=1;i<101;i++){

a[i]=rand()%100;

a[0]++;

}//for

cout<<"\nThe original elements are:\n";

for(i=1;i<101;i++){

cout<<setw(2)<<a[i]<<" ";

if(i%10==0)

cout<<"\n";

}//for

cout<<endl<<endl;

HeapSort(a,100);

return 0;

}//main