#include <iostream>
#include <fstream>

using namespace std;

/*
    MaxHeap
*/

#define Nmax 500003

#define Parent(i) i>>1
#define LeftSon(i) i<<1
#define RightSon(i) 1+i<<1

void InitHeap( int *H )
{
    for ( int i = 0; i < Nmax; ++i )
            H[i] = 0;
}

void DownHeap( int *H, int N, int poz )
{
    int k = poz;
    int j;

    do
    {
        j = k;

        if ( LeftSon(j) <= N && H[LeftSon(j)] > H[k] )   k = LeftSon(j);
        if ( RightSon(j) <= N && H[RightSon(j)] > H[k] ) k = RightSon(j);

        swap( H[k], H[j] );

    } while( j != k );
}

void UpHeap( int *H, int N, int poz )
{
    int k = poz;
    int j;

    do
    {
        j = k;

        if ( j > 1 && H[Parent(j)] > H[k] )  k = Parent(j);

        swap( H[k], H[j] );

    } while( j != k );
}

void InsertHeap( int *H, int &N, int key )
{
    H[ ++N ] = key;

    UpHeap( H, N, N );
}

void DeleteMax( int *H, int &N )
{
    H[1] = H[N];

    DownHeap( H, N, 1 );

    N--;
}

void ChangeHeap( int *H, int N, int poz, int value )
{
    int val = H[poz];
    H[poz] = value;

    if ( val > value )
            DownHeap( H, N, poz );
    else
            UpHeap( H, N, poz );
}



void MakeHeap( int *H, int N )
{
    for ( int i = N/2; i >= 1; i-- )
            DownHeap( H, N, i );
}

void HeapSort( int *H, int N )
{
    MakeHeap( H, N );

    for ( int i = N; i >= 2; i-- )
    {
        swap( H[1], H[i] );
        DownHeap( H, i - 1, 1 );
    }
}


int main()
{
    int H[500004], n = 0;


    n = 3;
    H[1] = 2;
    H[2] = 3;
    H[3] = 1;

    HeapSort(H,n);

    for ( int i = 1; i <= n;i++)
            cout<<H[i]<<" ";

    return 0;
}