//
//  Author: SUZUKI, RICARDO

//Heap Sort program
// last update on Saturday, April 26

#include<iostream>
#include<cstdlib>
#include<fstream>
#include<iomanip>

using namespace std;

int Many_int();
//PRECONDITION: there must be a .txt file with int
//POSTCONDITIN: returns the amount of int in the file

void fill_up_array(int array[]);
//PRECONDITION: receives an array
//POSTCONDITIN: fill it up with the numbers from
//			the input.txt file

void HeapSort(int array[], int n);
void Heap_Help(int array[],int i,int HeapSize);
//PRECONDITION: receives an array and its size
//POSTCONDITIN: sorts the array using heapsort
//		and merge the first two ones

void Print(int array[], int size);
//PRECONDITION: receives an array and its size
//POSTCONDITIN: prints the array to a file

void main(void)
{
	int	many_numbers = Many_int();
	
	// declare the array for differente sorts
	int *array_to_heap;
	array_to_heap = new int[many_numbers];

	// fill up array
	fill_up_array(array_to_heap);
	
	// call the sort function
	HeapSort(array_to_heap, many_numbers);
	Print(array_to_heap, many_numbers);
	

}

void Print(int array[], int size)
{
	ofstream outfile;
	outfile.open("output.txt");

	outfile<<"********* Heap Sort *********** "<<endl;
	for( int i=0; i< size ; i++)
	{
		outfile<< setw(10)<<array[i]<<endl;
	}
	
}

//**************** H E A P  S O R T *****************
void HeapSort(int array[], int n)
{
	int i;
	int HeapSize = n;
	
	for (i= HeapSize/2; i >= 1; i--)
		Heap_Help(array,i,HeapSize);
	
	for (i=n; i>=2; i--) {
		swap(array[i],array[1]);
		HeapSize--;
		Heap_Help(array,1,HeapSize);
	}
}

void Heap_Help(int array[],int i,int HeapSize)
{
	int left=2*i;
	int right=2*i+1;
	int largest;
	
	if ((left <= HeapSize) && 
		(array[left] > array[i]))
		largest = left;
	else
		largest = i;
	
	if ((right <= HeapSize) && 
		(array[right] > array[largest]))
		largest = right;
	
	if (largest != i) 
	{
		swap(array[i],array[largest]);
		Heap_Help(array,largest,HeapSize);
	}
}

// get integers from file and put in array
void fill_up_array(int array[])
{
	int dummy;
	int i=0;
	ifstream fill_array;
	fill_array.open("input.txt");
	
	while(!fill_array.eof())
	{	fill_array>>dummy;
	array[i] = dummy;
	i++;
	}
	
	fill_array.close();	
}

// counts how many numbers in the file
int Many_int()
{
	ifstream count_file;
	count_file.open("input.txt");
	if(!count_file)
	{
		cout<<"There is no file to read"<<endl;
		return EXIT_FAILURE;
	}
	
	int many_numbers=0;
	int dummy;
	
	while(!count_file.eof())
	{
		count_file>>dummy;
		many_numbers++;	
	}
	--many_numbers;
	count_file.close();
	return many_numbers;
}