/* 
 * File:   main.cpp
 * Author: speedemon
 *
 * Created on October 2, 2009, 7:09 PM
 */
#include <fstream>
#include <cstdlib>
#define InFile "algsort.in"
#define OutFile "algsort.out"

/*
 * 
 */

using namespace std;
ifstream in;
ofstream out;
class array
{
    int *v;
    unsigned size;
public:
    array();
    ~array();
    inline void swap( unsigned, unsigned );
    inline unsigned getsize(); //retuns the size of array
    inline bool check( unsigned, unsigned ); // checks if v[a] <= v[b]
    inline bool check_strict( unsigned, unsigned ); // checks if v[a] < v[b]
    inline void push( istream& ); // puts a new element in v
    void output( ostream& ); // outputs the array
};
array::array() //creat an array
{size=0;
        v=new int;
}
array::~array() //destroy an array
{
    delete[] v;
}
inline void array::swap( unsigned a, unsigned b )
{int aux=v[a];
    v[a]=v[b];
    v[b]=aux;
}
inline unsigned array::getsize()
{
    return size;
}
inline bool array::check( unsigned a, unsigned b )
{
    return v[a] <= v[b];
}
inline bool array::check_strict( unsigned a, unsigned b )
{
    return v[a] < v[b];
}
inline void array::push( istream& in )
{++size;
    v=(int*)realloc( (void*)v, size*sizeof(int) );
    in>>v[size-1];
}
inline void array::output( ostream& out )
{
    for( unsigned i=0; i < size; ++i ) out<<v[i]<<' ';
}
class HeapSort : public array
{
    void downheap( unsigned, unsigned );
    void make_heap( unsigned );
public:
    HeapSort();
    ~HeapSort();
    void sortheap( int, int );
};
HeapSort::HeapSort(): array()
{
    //constructor creating an array
}
HeapSort::~HeapSort()
{
}
void HeapSort::downheap( unsigned start, unsigned end )
{
    for( unsigned root=2*start+1; root < end; )
    {
        if( root+1 < end && check_strict( root, root+1 ) ) ++root;
        if( check( root, start ) ) return;
        swap( root, start );
        start=root;
        root=2*start+1;
    }
}
void HeapSort::make_heap( unsigned end )
{
    for( int start=end/2-1; start >= 0; --start )
        downheap( start, end );
}
void HeapSort::sortheap(int start , int end )
{make_heap( end );
    for( end=end-1; end >= start; --end )
    {
        swap( 0, end );
        downheap( 0, end );
    }
}
int main()
{int N; 
    HeapSort a;
    in.open(InFile);
    in>>N;
    while( N-- )
    {
        a.push(in);
    }
    a.sortheap( 0, a.getsize() );
    out.open(OutFile);
    a.output( out );
    return EXIT_SUCCESS;
}