#include<iostream>
using namespace std;
//大根堆，从小到达排序
int a[];
void swap(int &a,int &b)
{
a=a^b;
b=a^b;
a=a^b; }
void adjust(int *a,int root,int len)
{
int max=root;
int left=*root;
int right=*root+;
if(left<=len&&a[max]<a[left])
{
max=left; } if(right<=len&&a[max]<a[right])
{
max=right; }
if(max!=root)
{
swap(a[max],a[root]); adjust(a,max,len); } }
void bulidHeap(int *a,int len)
{ for(int i=len/;i>=;i--)
{
adjust(a,i,len); } } void heapSort(int *a,int len)
{
if(len>)
{
swap(a[],a[len]);
adjust(a,,len-);//调整为堆
heapSort(a,len-); } }
void output(int *a,int len)
{
for(int i=;i<=len;i++)
{
cout<<a[i]<<" "; }
cout<<endl; } int main()
{ while(!cin.eof())
{
int len;
cin>>len;
for(int i=;i<=len;i++)
{
cin>>a[i];
} bulidHeap(a,len); heapSort(a,len);
output(a,len); } return ; }
//一个大根堆的例子
//author:张小二
public class HeapSort {
public static void swap(int a[],int i,int j)
{ int temp=a[i];
a[i]=a[j];
a[j]=temp; }
//最重要的自上而下调整的方法。，最多的代码在此处，建队和堆排序都是靠他。
public static void adjust(int a[],int i,int len)//调整以i为根
{ while(true)
{
int largest=i;//寻找 i,2i+1,2i+2中的最大值
int r=2*i;
int l=2*i+1;
if(r<len&&a[r]>a[largest]) largest=r;
if(l<len&&a[l]>a[largest]) largest=l;
if(largest==i) break; swap(a,i,largest);
i=largest; } }
//建立堆，从最后一个非叶子开始
public static void bulid(int a[],int len)
{
display(a);
len=len-1;
for(int i=len/2;i>=0;i--)
{
adjust(a,i,len); } }
//堆排序
public static void heapSort(int a[])
{
bulid(a,a.length); int len=a.length-1;
while(len<1)
{
swap(a,0,len);
adjust(a,0,len);
len--; }
//after
display(a);
} public static void display(int a[])
{
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+" ");
}
System.out.println(); } /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={3,-3,5,6,-7,9,45};
heapSort(a); } }