//Sortowanie stogowe (heapsort)
//www.algorytm.org

import java.util.Scanner;
public class HeapSort {
    static int [] tab;
    static Scanner s =new Scanner(System.in);
    
    static void heapify (int[] tab, int heap_size, int i) {
        int largest, temp;
        int l=2*i+1, r=(2*i)+2;
        if (l<heap_size && tab[l]>tab[i])
            largest=l;
        else largest=i;
        if (r<heap_size && tab[r]>tab[largest])
            largest=r;
        if (largest!=i) {
            temp=tab[largest];
            tab[largest]=tab[i];
            tab[i]=temp;
            heapify(tab,heap_size,largest);
        }
    }
    
    static void budKopiec(int[] tab, int rozmiar){
    	//buduj kopiec poczynając od poprzednika ostatniego liścia schodząc w górę
        for (int i=(rozmiar/2)-1;i>=0;i--)
            heapify(tab,rozmiar, i);
    }
 
    static void sort(int[] tab, int rozmiar) {
        int temp;
        //Zapewnij ze drzewo spelnia warunek kopca
        budKopiec(tab, rozmiar);
        for (int i=rozmiar-1;i>0;i--) {
        	//w korzeniu jest najwiekszy element, przenies go na koniec i zmniejsz rozmiar kopca
            temp=tab[i];
            tab[i]=tab[0];
            tab[0]=temp;
            rozmiar--;
            //odbuduj kopiec, zaczynajac od korzenia
            heapify(tab,rozmiar,0);
        }
    }

    public static void main(String[] args) {
    	//Pobierz dane
        System.out.print("Podaj liczbe elementow:");
        int rozmiar = s.nextInt();
        tab=new int[rozmiar];
 
        for (int i=0;i<rozmiar;i++){
            System.out.print("Podaj element:");
            tab[i]= s.nextInt();
        }
        
        //Posortuj
        sort (tab,rozmiar);
        
        //Pokaz wynik
        System.out.print("Posortowane elementy");
        for (int i=0;i<rozmiar;i++){
   
            System.out.print(" "+ tab[i]);
        }
        System.out.println("\n");
    }
}