building a heap

[Fernanda]

UnderflowException.h

#pragma once

#include <exception>
using namespace std;

class UnderflowException: public exception
{
};


OverflowException.h
#pragma once

#include <exception>
using namespace std;

class OverflowException: public exception
{
};



Node.h
#pragma once

template <typename KEY, typename VALUE>
class Node
{
public:
	KEY key;
	VALUE value;

	Node( )
	{
	}

	Node(const KEY &key, const VALUE &value): key(key), value(value)
	{
	}
};
	



Main.cpp
#include <stdlib.h>
#include <iostream>
using namespace std;

#include "Heap.h"

int main()
{
	Heap<int,double> heap(30);

	for (int i = 0; i < heap.getMaximumSize(); i++)
	{
		int newValue = rand() % 100 + 1;
		heap.insert(newValue,(double)newValue);
	}

	try
	{
		heap.insert(0,0);
		cout << "We should not be here!" << endl;
	}
	catch (OverflowException &)
	{
		cout << "Caught overflow exception" << endl;
	}

	while (!heap.isEmpty())
		cout << heap.remove() << endl;

	try
	{
		heap.remove();
		cout << "We should not be here!" << endl;
	}
	catch (UnderflowException &)
	{
		cout << "Caught underflow exception" << endl;
	}

	system("pause");
	return EXIT_SUCCESS;
}





Heap.h
#pragma once

#include "UnderflowException.h"
#include "OverflowException.h"
#include "Node.h"

template <typename KEY, typename VALUE>
class Heap
{
private:
	int maximumSize;
	int lastUsedIndex;
	Node<KEY,VALUE> *array;

public:
	Heap (int maximumSize): maximumSize(maximumSize), lastUsedIndex(-1)
	{
		array = new Node<KEY,VALUE>[maximumSize];
	}




	void insert (const KEY &key, const VALUE &value)
	{






	}

	VALUE remove ( )
	{
		VALUE result;

		if (!isEmpty())
		{
			result = array[0].value;
			array[0] = array[lastUsedIndex--];
			reheapDown();
		}
		else
			throw UnderflowException();

		return result;
	}

	bool isEmpty()
	{
		return getSize() == 0;
	}

	bool isFull()
	{
		return getSize() == getMaximumSize();
	}

	int getSize()
	{
		return lastUsedIndex + 1;
	}

	int getMaximumSize()
	{
		return maximumSize;
	}

private:
	static int parentIndexOf(int index)
	{
		return (index - 1) / 2;
	}

	static int leftChildOf(int index)
	{
		return index * 2 + 1;
	}

	static int rightChildOf(int index)
	{
		return index * 2 + 2;
	}

	int largestChildOf (int index)
	{
		int result;
		int rightChildIndex = rightChildOf(index);
		int leftChildIndex = leftChildOf(index);

		if (rightChildIndex <= lastUsedIndex)
		{
			if (array[rightChildIndex].key > array[leftChildIndex].key)
				result = rightChildIndex;
			else
				result = leftChildIndex;
		}
		else if (leftChildIndex <= lastUsedIndex)
			result = leftChildIndex;
		else
			result = -1;

		return result;
	}

	void swap (int i, int j)
	{
		Node<KEY,VALUE> temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}




	void reheapUp ()
	{








	}

	void reheapDown ()
	{
		int current = 0;
		int largestChildIndex = largestChildOf(current);
		while (largestChildIndex > -1 && array[largestChildIndex].key > array[current].key)
		{
			swap(largestChildIndex,current);
			current = largestChildIndex;
			largestChildIndex = largestChildOf(current);
		}
	}
};

[androidapp]

Heap is top heavy, if a new item is greater than root, make it the new root and re balance the tree.