/*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;
Bottom up:
 - half of the array are leaves ( last half ) then we have to heapify the first n/2 values.
 - stability : not stable

 Top down
 - at first we start with a heap of 1 element and then we increase the heap size and swim the greater elements upwards
 - stability : not stable
*/


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

#define arr_size 10


using namespace std;

int counterAT, counterCT, counterAB, counterCB;

void swap(int *xp, int *yp)
{
	int temp = *xp;
	*xp = *yp;
	*yp = temp;
}

//Start Bottom-Up
void Bottom_Up(int arr[], int n, int root)
{
	int largest = root;
	int left = 2 * root + 1;
	int right = 2 * root + 2;

	counterCB++;
	if(left < n && arr[largest] < arr[left])
	{
		largest = left;
	}

	counterCB++;
	if (right < n && arr[largest] < arr[right])
	{
		largest = right;
	}

	if (largest != root)
	{
		swap(arr[root], arr[largest]);
		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 HeapSortBu(int arr[], int n)
{
	BuildHeapBU(arr, n);
	for ( int i = n - 1; i >= 1; i--)
	{
		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 << "\n";
}


// END BOTTOM-UP

//START TOP-DOWN

void RecursiveSwim(int arr[], int index)
{
	if (index == 0) return;
	else
	{
		int parent = (index - 1) / 2;

		counterCT++;

		if (arr[parent] < arr[index])
		{
			int buff = arr[index];
			arr[index] = arr[parent];
			arr[parent] = buff;

			counterAT += 3;

			RecursiveSwim(arr, parent);
		}
	}

}


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

	for (int heapsize = 1; heapsize < n; heapsize++)
	{
		RecursiveSwim(arr, heapsize);
	}
}

// END TOP-DOWN





int main()
{
	ofstream MyFile;
	MyFile.open("MyFile.csv");
	MyFile << "n,BU A average, BU C Average,BU T Average,TD A Average,TD C Average,TD T Average" << "\n";
	int arr1[Max_Size], arr2[Max_Size];
	srand((unsigned int)time(NULL));

	//Average case
	for (int n = 200; n <= 5000; n = n + 200)
	{
		for (int i = 0; i < n; i++)
		{
			arr1[i] = rand() % Max_Size;
			arr2[i] = arr1[i];
		}


		counterAT = 0;
		counterCT = 0;
		counterAB = 0;
		counterCB = 0;

        BuildHeapBU(arr1, n);
	    BuildheapTD(arr2, n);

		MyFile << n << "," << counterAB << "," << counterCB << "," << counterAB + counterCB << "," << counterAT << "," << counterCT << "," << counterAT + counterCT <<endl;

	  }
	//Best Case
	MyFile << "n, BU A Best, BU C Best, BU T Best,TD A Best, TD C Best, TD T Best " << "\n";
	for (int n = 200; n <= 5000; n = n + 200)
	{
		for (int i = 0; i < n; i++)
		{
			arr1[i] = i;

		}
		counterAB = 0;
		counterCB = 0;
		BuildHeapBU(arr1, n);

		for (int i = 0; i < n; i++)
		{
			arr2[i] = i;
			counterAT = 0;
			counterCT = 0;
			BuildheapTD(arr2, n);
		}
		MyFile << n << "," << counterAB << "," << counterCB << "," << counterAB + counterCB << "," << counterAT << "," << counterCT << "," << counterAT + counterCT << endl;
	}

	//Worst Case
	MyFile << "n, BU A Worst, BU C Worst, BU T Worst, TD A Worst, TD C Worst,TD T Worst" << "\n";
	for (int n = 200; n <= 5000; n = n + 200)
	{

		for (int i = 0; i < n; i++)
		{
			arr1[i] = n - i + 1;
			counterAB = 0;
			counterCB = 0;
			BuildHeapBU(arr1, n);
		}

		for (int i = 0; i < n; i++)
		{
			arr2[i] = n - i + 1;
			counterAT = 0;
			counterCT = 0;
			BuildheapTD(arr2, n);
		}

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

	MyFile.close();

	//correctness of Bottom-Up
	cout << "Array1:\n";
	int n = 9;
	for (int i = 1; i <= n; i++)
		arr1[i] = rand() % Max_Size;
	for (int i = 1; i <= n; i++)
		cout << arr1[i] << " ";
	cout << endl;

	cout << "Bottom-Up Heap:\n";
	BuildHeapBU(arr1, n);
	for (int i = 1; i <= n; i++)
		cout << arr1[i] << " ";
	cout << endl;

	//correctness of Top-Down
	cout << "Array2:\n";

	for (int i = 1; i <= n; i++)
		arr2[i] = rand() % Max_Size;
	for (int i = 1; i <= n; i++)
		cout << arr2[i] << " ";
	cout << endl;

	cout << "Top-Down Heap:\n";
		BuildHeapBU(arr1, n);
	for (int i = 1; i <= n; i++)
		cout << arr2[i] << " ";
	cout << endl;



	return 0;
}