// lab02_take1.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>

#define ARR_SIZE 10

using namespace std;

int counterCBU = 0;
int counterABU = 0;

//B O T T O M      U P
void heapify_BU(int arr[], int n, int i)
{
	int largest = i; //init the target as root
	int l = 2 * i + 1;
	int r = 2 * i + 2;
	counterCBU++;
	if (l < n && arr[l] > arr[largest])
		largest = l;
	counterCBU++;
	if (r < n && arr[r] > arr[largest])
		largest = r;
	if (largest != i)
	{
		swap(arr[i],arr[largest]);
		counterABU = counterABU + 3;
		heapify_BU(arr, n, largest);
	}
}

void buildHeap_BottomUp(int arr[], int n)
{
	//start  from the se
	for (int i = (n / 2)-1; i >= 0; i--)
		heapify_BU(arr, n, i);

}

void heapSort_BU(int arr[], int n)
{
	buildHeap_BottomUp(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]);
		//heapify the reduced heap
		heapify_BU(arr, i, 0);
	}

}

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

// T O P      D O W N
int retParent(int i)//returns the parent of a node
{
	return (i - 1) / 2;
}
int counterATD = 0;//counter for assignments
int counterCTD = 0;//counter for comparisons
void heapIncreaseKey(int arr[], int i)
{

		while (i > 0 && arr[retParent(i)] < arr[i])
		{
			counterCTD++;
			counterATD = counterATD + 3;
			swap(arr[i], arr[retParent(i)]);
			i = retParent(i);
		}
}

void maxHeapInsert(int arr[], int &heapSize)
{
	heapIncreaseKey(arr, heapSize);
	heapSize++;
}
// n - array length
void buildMaxHeap(int arr[], int n)
{
	int heapSize = 1;
	for (int i = 1; i <= n; i++)
		maxHeapInsert(arr, heapSize);
}

/*void averageCase(int incr, int max)
{
	for (int i = incr; i <= max; i = i + incr)
	{

	}
}*/

int main()
{
	int a[ARR_SIZE], b[ARR_SIZE];
	srand((unsigned int)time(NULL));




    //proof of correctness
	for (int i = 0; i < ARR_SIZE; i++)
	{
		a[i] = rand() % 1001;
		b[i] = a[i];
	}

	//proof of correctness for Top-Down
	cout << " Top - Down " << endl;
	cout << endl;
	cout << " The initial array: " << endl;
	printArray(a, ARR_SIZE);
	buildMaxHeap(a, ARR_SIZE);
	cout << " The heap: " << endl;
	printArray(a, ARR_SIZE);
	cout << "--------------------------------------------------------------------------------" << endl;


	//proof of correctness for Bottom-Up
	cout << " Bottom - Up" << endl;
	cout << endl;
	cout << " The array: \n";
	printArray(b, ARR_SIZE);
	cout << " Unsorted heap: \n";
	buildHeap_BottomUp(b, ARR_SIZE);
	printArray(b, ARR_SIZE);
	cout << " Sorted heap: \n";
	heapSort_BU(b, ARR_SIZE);
	printArray(b, ARR_SIZE);

	return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started:
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file