
// heap.cpp

#include "stdafx.h"

#include 
#include 
#include 
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;
}