package com.bupt.acm;

import java.util.Scanner;

public class HeapSort {

    private int getLeft(int i){
    
        return 2*(i+1)-1;
    }
    private int getRight(int i){
        return 2*(i+1);
    }
    public void heapSort(int[] numb){
        int length=numb.length;
        int size=length;
        //根据数组建堆
        for(int i=length/2;i>=0;i--){
            buildMinHeap(numb,i,size);
        }
        //将最小值移到最后元素并调整
        int tmp=0;
        for(int i=size-1;i>=0;i--){
            tmp=numb[0];
            numb[0]=numb[i];
            numb[i]=tmp;
            buildMinHeap(numb, 0,i);
        }
    }
    private void buildMinHeap(int[] numb,int i,int length){
        int largest=i;
        int left=getLeft(i);
        int right=getRight(i);
        
        if(left<length&&numb[largest]<numb[left]){
            largest=left;
        }
        if(right<length&&numb[largest]<numb[right]){
            largest=right;
        }
        if(largest==i){
            return;
        }else{
            int tmp=numb[i];
            numb[i]=numb[largest];
            numb[largest]=tmp;
            buildMinHeap(numb, largest,length);
        }
    }
    private void buildMaxHeap(int[] numb, int i,int length) {
        // TODO Auto-generated method stub
        int largest=i;
        int left=getLeft(i);
        int right=getRight(i);
        
        if(left<length&&numb[largest]>numb[left]){
            largest=left;
        }
        if(right<length&&numb[largest]>numb[right]){
            largest=right;
        }
        if(largest==i){
            return;
        }else{
            int tmp=numb[i];
            numb[i]=numb[largest];
            numb[largest]=tmp;
            buildMaxHeap(numb, largest,length);
        }
    }
    public static void main(String[] args){
        int[] result=null;
        int n=0;
        Scanner scanner=new  Scanner(System.in);
        HeapSort heapSort=new HeapSort();
        while(scanner.hasNext()){
            n=scanner.nextInt();
            result=new int[n];
            for(int i=0;i<n;i++){
                result[i]=scanner.nextInt();
            }
            heapSort.heapSort(result);
            for (int i = 0; i < result.length; i++) {
                System.out.print(result[i]+" ");
            }
            System.out.println();
        }
    }
}