
#include "pch.h"
#include 
#include 

using namespace std;

const int N = 1000000;

int a[N];

inline void swap_a (int i, int j)
{
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

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

void heapify(int i, int k)
// vytvorit hromadu z a[i] ... a[k]
// za predpokladu, ze a[i+1] ... a[k] jiz hromadu tvori
{
    while (2 * i + 1 <= k)
    {
        int v = 2 * i + 1;
        if (v + 1 <= k)
            if (a[v + 1] > a[v])
                v = v + 1;
        if (a[i] < a[v])
        {
            swap(a[i], a[v]);
            i = v;
        }
        else
            i = k + 1;
    }
}

void heapsort (int n)
// setridit a[0] ... a[n-1]
{
    for (int i = n-1;i >= 0;i--)
        heapify(i,n-1);

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

int main()
{
    srand (time(NULL));
    for (int i = 0; i < N; i++)
        a[i] = rand() % 10000;

    heapsort (N);

    /*
    for (int k = N-1; k >= 2; k--)
       for (int i = 0; i < k; i++)
          if (a[i + 1] < a[i])
              swap(a[i + 1], a[i]);
     */
    bool ok = true;
    for (int i = 0; i < N; i++)
    {
       // cout << a[i];
        if (i < N - 1 && a[i + 1] < a[i]) { ok = false; cout << " CHYBA"; }
        //cout << endl;
    }
    if (ok)
       cout << "O.K." << endl; 
}