/*
For the two ways of building the heap from an unordered array, we can conclude that the Bottom-Up approach is faster.
This happens because in the case of the Top-Down approach, the Heapify function is called on all the nodes, after the unordered heap was built.
In the Bottom-Up approach, the algorithm assumes that the leaves are already in place, so it only applies to n/2 nodes;
	running times: -Bottom-up : O(n)
	               -Top-down : O(nlog(n))
*/

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>

#define arr_size 10
#define max 5000

using namespace std;

int counterCB = 0;
int counterAB = 0;

//Bottom-Up
void Bottom_UP(int arr[], int n, int i)
{
	int largest = i; //init the target as root
	int l = 2 * i + 1;
	int r = 2 * i + 2;
	counterCB++;
	if (l < n && arr[l] > arr[largest])
		largest = l;
	counterCB++;
	if (r < n && arr[r] > arr[largest])
		largest = r;
	if (largest != i)
	{
		swap(arr[i], arr[largest]);
		counterAB = counterAB + 3;
		Bottom_UP(arr, n, largest);
	}
}

void buildHeapBU(int arr[], int n)
{

	for (int i = (n / 2) - 1; i >= 0; i--)
		Bottom_UP(arr, n, i);

}

void sort(int arr[], int n)
{
	buildHeapBU(arr, n);
	//one by one extract elements from the heap
	for (int i = n - 1; i >= 1; i--)
	{
		//move current root to end
		swap(arr[0], arr[i]);

		Bottom_UP(arr, i, 0);
	}

}

void print_array(int arr[], int n)
{
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << endl;
}

// Top-Down
int ReturnParent(int index)
{
	return (index - 1) / 2;
}
int counterAT = 0;
int counterCT = 0;
void Key(int arr[], int index)
{

	while (index > 0 && arr[ReturnParent(index)] < arr[index])
	{
		counterCT++;
		counterAT = counterAT + 3;
		swap(arr[index], arr[ReturnParent(index)]);
		index = ReturnParent(index);
	}
}

void HeapInsert(int arr[], int &size)
{
	Key(arr, size);
	size++;
}

void buildHeap(int arr[], int n)
{
	int size = 1;
	for (int i = 1; i <= n; i++)
		HeapInsert(arr, size);
}


int main()
{
	int arr1[arr_size], arr2[arr_size];
	srand((unsigned int)time(NULL));




	//proof of correctness
	for (int i = 0; i < arr_size; i++)
	{
		arr1[i] = rand() % 1001;
		arr2[i] = arr1[i];
	}

	//proof of correctness for Top-Down
	cout << " Top-Down: " << endl;
	cout << endl;
	cout << " The initial array is: " << endl;
	print_array(arr1, arr_size);
	buildHeap(arr1, arr_size);
	cout << " The heap is: " << endl;
	print_array(arr1, arr_size);
	cout << endl;


	//proof of correctness for Bottom-Up
	cout << " Bottom-Up:" << endl;
	cout << endl;
	cout << " The array is: \n";
	print_array(arr2, arr_size);
	cout << " The unsorted heap is: \n";
	buildHeapBU(arr2, arr_size);
	print_array(arr2, arr_size);
	cout << " The sorted heap is: \n";
	sort(arr2, arr_size);
	print_array(arr2, arr_size);

	// average

	ofstream MyFile1;
	MyFile1.open("MyFile1.csv");
	MyFile1 << "n,Bottom A Average,Bottom C Average ,Bottom T Average,Top A Average,Top C Average,Top T Average " << "\n";
	int arr3[max],arr4[max];
	for (int n = 200; n <= 5000; n = n + 200)
	{
		counterAB = 0;
		counterCB = 0;
		counterAT = 0;
		counterCT = 0;
		for (int m = 0; m < 5; m++)
		{
			for (int i = 0; i < n; i++) {

				arr3[i] = rand() % max;
				arr4[i] = arr3[i];
			}
			buildHeapBU(arr3, n);
			buildHeap(arr4, n);
		}
		counterAB = counterAB / 5;
		counterCB = counterCB / 5;
		counterAT = counterAT / 5;
		counterCT = counterCT / 5;

		MyFile1 << n << "," << counterAB << "," << counterCB << "," << counterAB + counterCB << "," << counterAT << "," << counterCT << "," << counterAT + counterCT << endl;
	}

	return 0;
}