#include <iostream>
#include <time.h>
 
using namespace std;
 
const int N = 1000;
 
int a [N];
 
inline  void swap (int i, int k)
{
    int t = a[i];
    a[i] = a[k];
    a[k] = t;
}
 
void heapify (int i, int k)
// vytvorit haldu s indexy i, ..., k
// za predpokladu, ze indexy i+1, ..., k jiz haldu tvori
{
    while (2*i+1 <= k) // levy existuje
    {
        int v = 2*i+1; // index leveho 
        if (v+1 <= k) // pravy existuje
            if (a [v+1] > a [v])  // pravy je vetsi
                v = v+1; // index vetsiho
 
        if (a [v] > a [i]) // porovnani vetsiho a prvku nahore
        {
            swap (v, i); // prohodime
            i = v; // pokracujeme s indexem v
        }
        else
        {
            i = k; // zastavime cylus
        }
    }
}
 
void heapSort (int n)
{
    for (int i = n-1; i >= 0; i--)
       heapify (i, n-1);
 
    swap (0, n-1);
 
    for (int k = n-2; k >= 1; k--)
    {
        heapify (0, k);
        swap (0, k);
    }
}
 
int main ()
{
    srand (time (nullptr));
    for (int i = 0; i < N; i++)
        a [i] = rand () % 10000;
 
    heapSort (N);
 
    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;
}

#include <iostream>
#include <time.h>
 
using namespace std;
 
const int N = 1000;
 
int a [N+1]; // a[0] nepouzivam
 
inline  void swap (int i, int k)
{
    int t = a[i];
    a[i] = a[k];
    a[k] = t;
}
 
void heapify (int i, int k)
// vytvorit haldu s indexy i, ..., k
// za predpokladu, ze indexy i+1, ..., k jiz haldu tvori
{
    while (2*i <= k) // levy existuje
    {
        int v = 2*i; // index leveho 
        if (v+1 <= k) // pravy existuje
            if (a [v+1] > a [v])  // pravy je vetsi
                v = v+1; // index vetsiho
 
        if (a [v] > a [i]) // porovnani vetsiho a prvku nahore
        {
            swap (v, i); // prohodime
            i = v; // pokracujeme s indexem v
        }
        else
        {
            i = k; // zastavime cylus
        }
    }
}
 
void heapSort (int n)
{
    for (int i = n; i >= 1; i--)
       heapify (i, n);
 
    swap (1, n);
 
    for (int k = n-1; k >= 2; k--)
    {
        heapify (1, k);
        swap (1, k);
    }
}
 
int main ()
{
    srand (time (nullptr));
    a[0] = 0;
    for (int i = 1; i <= N; i++)
        a [i] = rand () % 10000;
 
    heapSort (N);
 
    bool ok = true;
    for (int i = 1; i <= N; i++)
    {
        cout << a [i];
        if (i < N && a[i+1] < a[i]) { ok = false; cout << " CHYBA"; }
        cout << endl;
    }
 
    if (ok)
       cout << "O.K." << endl;
}