// heap.cpp
 
#include "stdafx.h"
 
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
 
const int N = 1000000;
 
 
int a[N];
 
void swap (int &x, int &y){
    int z = x;
    x = y;
    y = z;
}
 
void change (int i, int j){
    int z = a[i];
    a[i] = a[j];
    a[j] = z;
}
 
void makeheap(int i, int j){
    while (2*i+1 <= j){
 
        int v = 2*i +1;
        if(v+1 <= j && a[v] < a[v+1])
            v = v+1;
        if(a[v] > a[i]){
            swap(a[i], a[v]);
            i=v;
        }
        else i=j; //ukonceni cyklu
    }
}
 
void heapsort (int n)
{
    for (int i=n/2;i>=0;i--)
        makeheap (i,n-1);
 
    for (int i=n-2;i>=0;i--)
    {
        swap (a[0],a[i+1]);
        makeheap (0,i);
    }
 
}
 
void init (int n){
    for(int i=0; i< n; i++)
        a[i] = rand () % (n);
}
 
void vypis (int n){
    for(int i=0; i< n; i++)
        cout << a[i] << " ";
    cout << endl;
}
 
void kontrola (int n)
{
    for(int i=0; i< n-1; i++)
        assert (a[i]<=a[i+1]);
 
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    int n = 100;
    assert (n <= N);
    init (n);
    if (n <= 100) vypis (n);
    heapsort (n);
    if (n <= 100) vypis (n);
    kontrola (n);
    system ("pause");
    return 0;
}