// CS301P Lab 12 Problem KST Learning

#include<iostream>
#include<conio.h>
using namespace std;

class Heap
{
	private:
		int *array;
	public:
		Heap(int size)
		{
			array = new int[size++];	
		}	
		
		void buildHeap(int *a, int size)
		{
			int loop;
			for(int i=1; i<=size; i++)
			{
				array[i] = a[i-1];
			}
			
			do{
				loop = 0;
				for(int i=size/2; i>0; i--)
				{
					loop += percolateDown(i,size);
				}
			}while(loop > 0);
			
		}
		
		int percolateDown(int index, int size)
		{
			int ret = 0;
			int temp;
			if(array[index] > array[index*2] && (index*2) <= size)
			{
				temp = array[index];
				array[index] = array[index*2];
				array[index*2] = temp;
				ret++;
			}
			if(array[index] > array[index*2+1] && (index*2+1) <= size)
			{
				temp = array[index];
				array[index] = array[index*2+1];
				array[index*2+1] = temp;
				ret++;
			}
			return ret;
		}
		
		void traverse(int size)
		{
			for(int i=1; i<=size; i++)
			{
				cout << array[i] << " ";
			}
		}
};

main()
{
	int size = 16;
	int array[size] = {18, 31, 82, 85, 37, 20, 23, 79, 47, 51, 96, 97, 42, 94, 57, 29};
	Heap obj(size);
	obj.buildHeap(&array[0],size);
	cout << "*** Min Heap Using Build Heap Method ***\n\n";
	obj.traverse(size);
	getch();
	return 0;
}