// HeapSort.cpp 

#include "stdafx.h"
#include <time.h>    
#include <iostream>
#include <string>
using namespace std;

const int N = 200;

int a [N];

void heapify (int i, int k)
{
	while (2*i+1 <= k) 
	{
		// if (!(a[i] >= a[2*i+1] && (2*i+2 > k || a[i] >= a[2*i+2])))
  	    int p = 2*i+1; 
		if (p+1 <= k) 
  		   if (a[p+1] > a[p])
				p = p+1;
		if (a[i] < a[p])
		{
			int pom = a[p];
			a[p] = a[i];
			a[i] = pom;
			i = p; //Zde pokracujeme
		}
		else i=k+1; //Konec
	}
}

void heapsort (){
	for (int i = N-1; i>=0; i--){
		heapify (i, N-1);
	}
	for(int k = N-1; k>0; k--){
		int pom = a[k];
		a[k] = a[0];
		a[0] = pom;
		heapify(0, k-1);
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	/*
	a [0] = 1;
	a [1] = 10;
	a [2] = 20;
	a [3] = 5;
	a [4] = 7;
	a [5] = 8;
	*/

    /* initialize random seed: */
    srand (time (NULL));

	for (int i = 0; i < N; i++)
		a[i] = rand () % 100;

	heapsort ();

	bool ok = true;
	for (int i = 0; i < N; i++)
	{
		if (i+1 < N)
			if (a[i+1] < a[i]) ok = false;
		cout << a[i] << " ";
	}
	cout << endl;

	if (ok)
		cout << "O.K." << endl;
	else
		cout << "ERROR" << endl;

	cout << "Hotovo" << endl;
	system ("pause");

	return 0;
}