#include "stdafx.h"
#include <iostream>
#include <string>
#include <ctime>
using namespace std;
 
// const int n = 7;
// int a[n] = { 20, 7, 15, 1, 3, 10, 12 };
 
const int n = 1000000;
int a[n];
 
void swap (int i, int k)
{
    int c;
    c = a[i];
    a[i] = a[k];
    a[k] = c;
}
 
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 = w + 1;
        if (a[w] > a[i])
        {
            swap (i, w);
            i = w;
        }
        else
            i = k + 1;
    }
}
 
void heapSort ()
{
    for (int k = n - 1; k >= 0; k--)
    {
        heapify (k, n - 1);
    }
    for (int k = n - 1; k > 0; k--)
    {
        swap (0, k);
        heapify (0, k-1);
    }
 
}
 
int main (int argc, char * argv[])
{
    srand (time (nullptr));
    for (int i = 0; i < n; i++)
        a[i] = rand () % 10000;
 
    heapSort ();
 
    for (int i = 0; i < n; i++)
    {
        // cout << a[i];
        if (i > 0)
            if (a[i-1] > a[i])
                cout << " Chyba";
        // cout << endl;
    }
 
    cout << "Konec programu" << endl;
    system ("pause");
    return 0;
}