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


#define Max_Size 5001

using namespace std;

int counterAT, counterCT, counterAB, counterCB;

void Bottom_Up(int arr[], int n, int root)
{
    int largest = root;
    int leftChildIndex = 2 * root + 1;
    int rightChildIndex = 2 * root + 2;

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

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

    if (largest != root)
    {
        int buffer = arr[root];
        arr[root] = arr[largest];
        arr[largest] = buffer;

        counterAB += 3;
        Bottom_Up(arr, n, largest);
    }
}

void BuildHeapBU(int arr[], int n)
{
    int i;
    for (i = (n / 2) - 1; i >= 0; i--)
    {
        Bottom_Up(arr, n, i);
    }
}

void HeapSortBu(int arr[], int n)
{
    BuildHeapBU(arr, n);
    int i;
    for (i = n -1 ; i >= 0; i--)
    {
        int buffer = arr[0];
        arr[0] = arr[i];
        arr[i] = buffer;

        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 iterative_swim(int arr[], int index)
{

    while ((index > 0) && (arr[(index - 1) / 2] < arr[index]))
    {
        counterCT++;

        int buff = arr[index];
        arr[index] = arr[(index - 1) / 2];
        arr[(index - 1) / 2] = buff;

        counterAT += 3;
        index = (index - 1) / 2;
    }
    counterCT++;
}

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));
    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;

      }
    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;
    }
    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();

    cout << "Bottom:\n";
    int n = 10;
    for (int i = 1; i <= n; i++)
        arr1[i] = rand() % Max_Size;
    for (int i = 1; i <= n; i++)
        cout << arr1[i] << " ";
    cout << endl;
    HeapSortBu(arr1, n);
    for (int i = 1; i <= n; i++)
        cout << arr1[i] << " ";
    cout << endl;





    /*cout << "Top:\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;
     HeapSortBu(arr2, n);
    for (int i = 1; i <= n; i++)
        cout << arr2[i] << " ";
    cout << endl;
 */

    return 0;
}