#include <iostream>
using namespace std;
void heapsort(int *arr,int len);
void heapadjust(int *arr,int i,int len);
int main() {
int i,n;
cout<<"Please print the number of the arr n"<<endl;
cin>>n;
cout<<"Please print all of the arr"<<endl;
int *arr=new int[n+10];
for(i=0;i<n;i++)cin>>arr[i];
heapsort(arr,n);
cout<<"Through the heapsort"<<endl;
for(int i=0;i<n;i++)cout<<arr[i]<<endl;
return 0;
}
void heapsort(int *arr,int len)
{
int i;
for(i=len/2-1;i>=0;i--)heapadjust(arr,i,len);
for(i=len-1;i>0;i--)
{
swap(arr[i],arr[0]);
len-=1;
heapadjust(arr,0,len);
}
}
void heapadjust(int *arr,int i,int len)
{
int j;
for(j=2*i+1;j<len;j=2*j+1)
{
if(j+1<len&&arr[j+1]>arr[j])j+=1;
if(arr[j]>arr[i])
{
swap(arr[i],arr[j]);
i=j;
}
else
{
break;
}
}
}
