/*	
Heap, MinHeap, MaxHeap ADT (Array Style) - By Kevin Jenkins
Initilize with the following structure
Heap<TYPE, OPTIONAL INITIAL ALLOCATION SIZE>
MinHeap<TYPE, OPTIONAL INITIAL ALLOCATION SIZE>
MaxHeap<TYPE, OPTIONAL INITIAL ALLOCATION SIZE>

Has the following member functions
insert - adds an item to the end of the heap, or the appropriate location in the min/max heap
peek - returns a reference to the root node
del - deletes an item from the end of the heap, or the root node in a min/max heap
size - returns the number of elements in the heap
clear - deletes all elements in the heap

EXAMPLE

#include "heap.cpp"

void main(void)
{
	MinHeap<int> A;
	MinHeap<int> B;

	A.insert(5);
	A.insert(15);
	A.insert(1);

	B=A;

	A.peek(); // 1
	A.del();
	A.peek(); // 5
	
	B.insert(0);
	B.peek(); // 0
	B.del();
	B.peek(); // 1
	B.del();
	B.peek(); // 5
}

*/

#ifndef __HEAP_H
#define __HEAP_H

#include "list.cpp"

template <class heap_type, unsigned long allocation_size_arg=1L>
class Heap
{
public:
	Heap();
	~Heap();
	Heap(const Heap& original_copy);
	Heap& operator= (const Heap& original_copy);
	void insert(const heap_type& input);
	const heap_type& peek(void);
	void del(void);
	const unsigned long size(void);
	void clear(void);
		
protected:
	List<heap_type, allocation_size_arg> data;
};

template <class heap_type, unsigned long allocation_size_arg=1L>
class MinHeap : public Heap<heap_type, allocation_size_arg>
{
public:
	void insert(const heap_type& input);
	void del(void);
};

template <class heap_type, unsigned long allocation_size_arg=1L>
class MaxHeap : public Heap<heap_type, allocation_size_arg>
{
public:
	void insert(const heap_type& input);
	void del(void);
};

template <class heap_type, unsigned long allocation_size_arg>
Heap<heap_type, allocation_size_arg>::Heap()
{
	// Nothing to do, List data takes care of itself
}

template <class heap_type, unsigned long allocation_size_arg>
Heap<heap_type, allocation_size_arg>::~Heap()
{
	// Nothing to do, List data takes care of itself
}

template <class heap_type, unsigned long allocation_size_arg>
Heap<heap_type, allocation_size_arg>::Heap(const Heap& original_copy)
{
	data=original_copy.data;
}

template <class heap_type, unsigned long allocation_size_arg>
Heap<heap_type, allocation_size_arg>& Heap<heap_type, allocation_size_arg>::operator= (const Heap& original_copy)
{
	if ((&original_copy) != this)
		data=original_copy.data;
	
	return *this;
}

template <class heap_type, unsigned long allocation_size_arg>
void Heap<heap_type, allocation_size_arg>::clear (void)
{
	data.clear();
}

template <class heap_type, unsigned long allocation_size_arg>
void Heap<heap_type, allocation_size_arg>::insert(const heap_type& input)
{
	// A heap adds new items to the end of the list
	data.insert(input);
}

template <class heap_type, unsigned long allocation_size_arg>
void Heap<heap_type, allocation_size_arg>::del(void)
{
	// A heap removes items from the end of the list
	data.del();
}

template <class heap_type, unsigned long allocation_size_arg>
const unsigned long Heap<heap_type, allocation_size_arg>::size(void)
{
	return data.size();
}

template <class heap_type, unsigned long allocation_size_arg>
const heap_type& Heap<heap_type, allocation_size_arg>::peek(void)
{
	return data[0L];
}

template <class heap_type, unsigned long allocation_size_arg>
void MinHeap<heap_type, allocation_size_arg>::insert(const heap_type& input)
{
	heap_type temp;
	unsigned long position;
	
	// A heap adds new items to the end of the list
	data.insert(input);
	
	// A minheap has the property that every parent is less than its children.
	// If this node is less than its parent then swap it until the property is satisfied
	position=data.size()-1L;
	while (position!=0L && data[position] < data[(position-1L)/2L])
	{
		temp=data[(position-1L)/2L];
		data[(position-1L)/2L]=data[position];
		data[position]=temp;
		position=(position-1L)/2L;
	}
}

template <class heap_type, unsigned long allocation_size_arg>
void MaxHeap<heap_type, allocation_size_arg>::insert(const heap_type& input)
{
	heap_type temp;
	unsigned long position;
	
	// A heap adds new items to the end of the list
	data.insert(input);
	
	// A maxheap has the property that every parent is greater than its children.
	// If this node is greater than its parent then swap it until the property is satisfied
	position=data.size()-1L;
	while (position!=0L && data[position] > data[(position-1L)/2L])
	{
		temp=data[(position-1L)/2L];
		data[(position-1L)/2L]=data[position];
		data[position]=temp;
		position=(position-1L)/2L;
	}
}

template <class heap_type, unsigned long allocation_size_arg>
void MinHeap<heap_type, allocation_size_arg>::del(void)
{
	unsigned long position=0L;
	// MinHeaps and MaxHeaps remove the parent and replace it with the lesser / greater child respectively
	
	// Find out which child is less
	while (position*2L + 1L < data.size())  // As long as there is a left child
	{
		if (position*2L + 2L >= data.size()) // if there is no right child
		{
			position=position*2L + 1L; // Then the one to swap is the left child
		}
		else
		{
			if (data[position*2L + 1L] < data[position*2L + 2L])  // Find out whether the left or right child is less
				position=position*2L + 1L;
			else
				position=position*2L + 2L;
		}
		
		// Overwrite the parent with the lesser child
		data[(position-1L) / 2L] = data[position];
	}
	
	// delete the last duplicate node
	data.del(position);
}

template <class heap_type, unsigned long allocation_size_arg>
void MaxHeap<heap_type, allocation_size_arg>::del(void)
{
	unsigned long position=0L;
	// MinHeaps and MaxHeaps remove the parent and replace it with the lesser / greater child respectively
	
	// Find out which child is less
	while (position*2L + 1L < data.size())  // As long as there is a left child
	{
		if (position*2L + 2L >= data.size()) // if there is no right child
		{
			position=position*2L + 1L; // Then the one to swap is the left child
		}
		else
		{
			if (data[position*2L + 1L] > data[position*2L + 2L])  // Find out whether the left or right child is greater
				position=position*2L + 1L;
			else
				position=position*2L + 2L;
		}
		
		// Overwrite the parent with the greater child
		data[(position-1L) / 2L] = data[position];
	}
	
	// delete the last duplicate node
	data.del(position);
}

#endif