// HeapSort.cpp : 
 
#include "stdafx.h"
#include <string>
#include <iostream>
#include <cstdlib>
using namespace std;
 
const int N=100;
int a[N];
 
void heapify(int i, int k){
  while(2*i+1<=k) {
	int p;	
	p=2*i+1;
	if(p+1 <= k) 
		if(a[p]<a[p+1]) p=p+1;
	if(a[p]>a[i]){
		int q;
		q=a[p];
		a[p]=a[i];
		a[i]=q;
		i=p;
	}	else {
		i=k; // konec naší smyčky
	}
  }
}
 
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[0];
		a[0] = a[k];
		a[k] = pom;
		heapify(0, k-1);
	}
}
 
void print()
{
	for (int i = 0; i< N; i++)
	{
		if (i < N-1)
		{
			if (a[i] > a[i+1]) cout << "chyba" <<endl;
		}
 
		cout << a[i] << ", ";
	}
	cout << endl;
}
 
int _tmain(int argc, _TCHAR* argv[])
{
	srand(0);
	for (int i=0; i< N; i++)
		a[i] = rand() %100;
	heapSort();
	print();
	cout << "Konec - stisknete enter" << endl;
 
	char c;
	cin >> c;
 
 
	return 0;
}