// Lab2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include "Profiler.h"

#define SIZE 1000

void heapfy(int a[],int i, int size_heap)
{
	int left = 2 * i;
	int right = 2 * i + 1;
	int largest = i;
	if (left < size_heap && a[left] > a[largest])
	{
		largest = left;
	}

	if (right < size_heap && a[right] > a[largest])
	{
		largest = right;
	}
	if (i != largest)
	{
		std::swap(a[largest], a[i]);
		heapfy(a, largest, size_heap);
	}
}

void bubble_key(int a[], int pos, int key)
{

	a[pos] = key;

	while (pos>1 && a[pos] > a[pos/2])
	{
		std::swap(a[pos], a[pos / 2]);
		pos = pos / 2;
	}

}

void insert_heap(int a[], int &size, int key)
{
	size++;
	a[size] = INT_MIN;
	bubble_key(a, size, key);
}
// top down aproach
void build_heap_td(int arr[], int size_arr)
{
	int heap_size = 0;
	for (int i = 1; i < size_arr - 1;i++)
	{

		insert_heap(arr, heap_size, arr[i]);
	}

}
// bottom up aproach
void build_heap_bu(int a[],int size)
{
	for (int i = size/2; i > 0; i--)
		heapfy(a, i, size);

}

void print_arr(int arr[], int size)
{
	for (int i = 1; i < size; i++)
		std::cout << arr[i] << " ";
	std::cout << "\n";
}

void heapsort(int a[],int size)
{
	build_heap_td(a, size);
	print_arr(a, size);
	int end = size - 1;
	while (end > 1)
	{
		//print_arr(a, size);
		std::swap(a[end], a[1]);
		heapfy(a, 1, end);
		end--;
	}
}

void test_heapsort(int n)
{
	int size = n+1;
	int *a= new int[size];

	FillRandomArray<int>(a, size, 0, 1000);

	heapsort(a, size);
	print_arr(a, size);

	delete[] a;
}

int main()
{
	test_heapsort(10);

}