// heap.cpp

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


Heap::Heap()
{
	size=11;
	array = new int[size];
	marke=0;
}
	
Heap::Heap(int size)
{
	array = new int[size+1];
	this->size=size+1;
	marke=0;
}

Heap::~Heap()
{
	delete [] array;
}

int Heap::getSize()
{
	return marke;
}

int Heap::getMax()
{
	return size;
}

bool Heap::isEmpty(){
	return marke==0;
}

bool Heap::isFull()
{
	return marke==size-1;
}

void Heap::clear() {
	
	for(int i=0; i<size; i++)
	{	
		array[i]=NULL;
	}
	marke=0;
}

void Heap::insert(int val)
{
	if(isFull())
	{
		cout << "QueueFullException: value " << val << " was not inserted!"  << endl;
	}
	else
	{
		array[0] = val;
		int pos = ++marke;
		while( array[0] < array[pos/2] )
		{
			array[pos] = array[pos/2];
			pos=pos/2;
		}
		array[pos]=array[0];
	}
}

int Heap::deleteMin()
{
	if(isEmpty())
	{
		cout << "QueueEmptyException" << endl;
	}
	else
	{
		int min = array[1];
		array[1]=array[marke--];				
		percolateDown(1);
		return min;
	}
	return NULL;
}

void Heap::percolateDown(int start) 
{
	int pos = start;
	int tmp = array[pos];

	while( 2*pos <= marke )
	{
		int child = pos*2;

		if(child < marke && array[child+1]<array[child])
		{
			child++;
		}

		if(array[child]<tmp)
		{
			array[pos]=array[child];
			pos=child;
		}
		else
		{
			break;
		}
	}
	array[pos]=tmp;
}

void Heap::print()
{
	if(isEmpty())
	{
		cout << "Heap is empty!" << endl;
	}
	else
	{
		for(int i=0; i<marke; i++)
		{	
			cout << i+1 << ": " << array[i+1] << endl;
		}
	}
}