#include <iostream>

using namespace std;

// Bottom UP
void heapify(int* tree, int n, int root);
void buildHeap(int* tree, int n);


void swap(int* a, int* b)
{
	int aux = *a;
	*a = *b;
	*b = aux;
}

// Top Down
void heapIncreaseKey(int *tree, int i, int key)
{
    if(key >= tree[i])
    {
        tree[i] = key;
        while((i > 1) && (tree[(i/2) - 1] < tree[i]))
        {
            swap(&tree[i],&tree[(i/2)-1]);
            i = (i / 2 ) - 1;
        }
    }
}

void maxHeapInsert(int *tree, int key, int hSize)
{
    hSize += 1;
    heapIncreaseKey(tree,hSize,key);
}

void buildMaxHeap(int *tree, int n)
{
    for(int i = 2 ; i < n ; i++)
        maxHeapInsert(tree,tree[i],i);
}

// Heap Sort
//void swap(int* a, int* b);
void heapSort(int* tree, int n);

// Printuri
void printArray(int *a, int n);
void printHeap(int* tree, int n);

int main()
{
	int tree[] = { 1 , 3 , 5 , 4 , 6 , 13 , 10 , 9 , 8 , 15 , 17 };
	int n = sizeof(tree) / sizeof(tree[0]);
	buildHeap(tree, n);
	printHeap(tree, n);

    cout << '\n';

	int arr[] = { 12 , 11 , 13 , 5 , 7 , 6 };
	int n2 = sizeof(arr) / sizeof(arr[0]);
	heapSort(arr, n2);
	printArray(arr,n2);

	cout << '\n';

	int tree2[] = { 1 , 3 , 5 , 4 , 6 , 13 , 10 , 9 , 8 , 15 , 17 };
	int n3 = sizeof(tree2) / sizeof(tree2[0]);
	buildMaxHeap(tree2,n3,1);
	printHeap(tree2, n3);

	cout << '\n';

	int a = 10;
	int b = 5;
	swap(a,b);
	cout << a << " " << b;
}

void heapify(int* tree, int n, int root)
{
	int max = root;
	int leftChild = 2 * root + 1;
	int rightChild = 2 * root + 2;

	if (leftChild < n && tree[leftChild] > tree[max])
		max = leftChild;

	if (rightChild < n && tree[rightChild] > tree[max])
		max = rightChild;

	if (max != root)
	{
		swap(&tree[root], &tree[max]);
		heapify(tree, n, max);
	}
}

void heapSort(int* tree, int n)
{
	for (int i = n / 2 - 1; i >= 0; i--)
		heapify(tree, n, i);
	for (int i = n - 1; i >= 0; i--)
	{
		swap(tree[0], tree[i]);
		heapify(tree, i, 0);
	}
}

void buildHeap(int* tree, int n)
{
	int start = (n / 2) - 1;
	for (int i = start; i >= 0; i--)
		heapify(tree, n, i);
}

void printHeap(int *tree, int n)
{
    for(int i = 0 ; i < n ; i++)
        cout << tree[i] << " ";
}

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