
#include 
using namespace std;

const int N = 10;
int a[N] = { 20, 30, 40, 7, 5, 80, 22, 33, -1, -2 };

void swap (int& x, int& y)
{
    int t = x;
    x = y;
    y = t;
}

void heapify (int i, int k)
{
    while (2*i+1 <= k)
    {
        int v = 2 * i + 1;
        if (v + 1 <= k && a[v + 1] > a[v])
            v = v + 1;
        if (a[i] < a[v])
        {
            swap (a[i], a[v]);
            i = v;
        }
        else
        {
            // i = k + 1;
            break;
        }
    }

}

void heapsort()
{
    for (int i = N - 1; i >= 0; i--)
        heapify(i, N - 1);

    for (int k = N - 1; k > 0; k--)
    {
        swap (a[0], a[k]);
        heapify (0, k - 1);
    }
}

int main ()
{
    heapsort();

    for (int i = 0; i < N; i++)
        cout << a[i] << endl;

    cout << "O.K" << endl;
}