#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;
 
const int n = 1000000;
 
// int a[n] = { 7, 1, 12, 2, 8, 5, 20, 3 };
int a[n];
 
void swap (int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}
 
void heapify (int i, int k)
{
    while (2 * i + 1 <= k)
    {
        int w = 2 * i + 1;
        if (w + 1 <= k && a[w+1] > a[w])
            w += 1; // w = w + 1
        if (a[i] < a[w])
        {
            swap (a[i], a[w]);
            i = w;
        }
        else
        {
            i = k;
        }
    }
}
 
void heapSort (int p)
{
    for (int k = p - 1; k >= 0; k--) {
        heapify (k, p - 1);
    }
 
    for (int k = p - 1; k > 0; k--) {
        swap (a[0], a[k]);
        heapify (0, k - 1);
    }
 
}
 
#include <ctime>
int main ()
{
    srand (time (nullptr));
    for (int i = 0; i < n; i++)
        a[i] = rand () % 10000;
 
    heapSort (n);
 
    for (int i = 0; i < n; i++)
    {
        // cout << a[i] << endl;
        if (i < n - 1)
            if (a[i] > a[i + 1])
            {
                cout << "Chyba";
                exit (0);
            }
    }
 
    cout << "Konec programu" << endl;
    system ("pause");
    return 0;
}