/*
 * HeapSort.cpp
 *
 *  Created on: 13 Ara 2011
 *      Author: blog.asosyalbebe.com
 */
#include <iostream>
#include <stdlib.h>

using namespace std;

void heapsort(int array[], int size);
void buildheap(int array[], int size);
void percolateDown(int heap[], int size, int id);

void printArray(int array[], int size) {
	for(int i=0; i<size; i++) {
		cout << array[i] << " ";
	}
	cout << endl;
}

int main() {
	int size = 20;
	int arrayToSort[size];
	for(int i=0; i<size; i++)
		arrayToSort[i] = 1+rand()%99; // between 1 and 99
	printArray(arrayToSort, size);

	heapsort(arrayToSort, size);

	printArray(arrayToSort, size);
}

void heapsort(int array[], int size) {
	buildheap(array, size);
	int heapsize = size;

	for(int i=size-1; i>0; i--) {
		int temp = array[i];
		array[i] = array[0];
		array[0] = temp;
		heapsize--;
		percolateDown(array, heapsize, 0);
	}
}

void buildheap(int array[], int size) {
	for(int i=size/2; i>=0; i--) {
		percolateDown(array, size, i);
	}
}

void percolateDown(int array[], int size, int id) {
	int current = id;
	int max;
	while(true) {
		int left = current*2+1;
		int right = current*2+2;
		if(left >= size)
			return;
		else if(right >= size)
			max = left;
		else if(array[left] > array[right])
			max = left;
		else if(array[left] < array[right])
			max = right;
		if(array[max] > array[current]) {
			int temp = array[max];
			array[max] = array[current];
			array[current] = temp;
			current = max;
		} else
			return;
	}
}