// heap.cpp : Defines the entry point for the console application.
// dama.cpp 
 
#include "stdafx.h"
 
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
 
const int N = 1000000;
int a [N];
 
void change(int i, int j){
    int pom;
    pom= a[i];
    a[i]=a[j];
    a[j]=pom;
}
 
void swap(int &c, int &k){
    int pom;
    pom=c;
    c=k;
    k=pom;}
 
void heap(int i, int j) {	
    while((2*i+1) <= j ) {
        int levy = 2*i+1;
        int v = levy;
        if((2*i+2) <= j) {
            int pravy = 2*i+2;
            if (a[pravy] > a[levy] ) 
                v = pravy;
        }
        if(a[i] < a[v] ) {
            swap(a[i], a[v]);
            i = v;
        } else {
            i = j;
        };
    }
}
 
void heapsort(int n){
 
    assert (n <= N && n > 0);
 
    for(int i=n-1;i>=0;i--) {
        heap(i,n-1);
    };
 
    for(int i=n-1;i>=1;i--) {
        swap(a[0],a[i]);
        heap(0,i-1);
    };
};
 
void vypis(int n)
{
    for (int i=0; i<n; i++)
    {
        cout << a[i] << ", ";
    }
    cout << endl;
};
 
void kontrola(int n)
{
    for(int i=1; i<n; i++)
    {
       assert (a[i-1] <= a[i]);
    }
};
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    int n = 900000;
    assert (n <= N);
 
    for (int i=0; i<n; i++)
        a[i] = rand () % n;
 
    if (n <= 1000) vypis (n);
    cout << " ----- " << endl;
    heapsort (n);
    if (n <= 1000) vypis (n);
    kontrola;
 
    system ("pause");
    return 0;
}