mansour heap

/*
	Heap Data Structure
	cps 272
	4-20-2016
*/
#include <iostream>
using namespace std;

class HeapItem
{
private:
	int m_key;
public:
	HeapItem(int k = 0) : m_key(k) {}
	void setKey(int k) { m_key = k; }
	int getKey() { return m_key; }
};

class Heap
{
private:
	HeapItem *m_elements;	// pointer to dynamic array
	int m_numElements;
	int m_heapLength;
public:
	Heap(int sz = 10);
	~Heap() { delete[] m_elements; }
	bool Enqueue(int k);
	HeapItem *Dequeue();
	void print();
	void ReHeapDown(int root, int bottom);
	void ReHeapUp(int root, int bottom);
};

Heap::Heap(int sz)
{
	m_elements = new HeapItem[sz];
	m_numElements = 0;
	m_heapLength = sz;
}

bool Heap::Enqueue(int k)		// Add
{
	if (m_numElements < m_heapLength)
	{
		HeapItem *temp = new HeapItem(k);
		m_elements[m_numElements] = *temp;
		ReHeapUp(0, m_numElements);
		m_numElements++;
	}
	return false;
}

HeapItem *Heap::Dequeue()
{
	HeapItem *temp = new HeapItem(m_elements[0].getKey());
	m_numElements--;
	m_elements[0] = m_elements[m_numElements];
	ReHeapDown(0, m_numElements - 1);
	if (m_numElements == 0)
		return nullptr;
	else
		return temp;
}

void Heap::ReHeapDown(int root, int bottom)
{
	int leftChild = root * 2 + 1;
	int rightChild = root * 2 + 2;
	int maxChild;

	if (leftChild <= bottom)
	{
		if (leftChild == bottom)
			maxChild = leftChild;
		else
		{
			if (m_elements[leftChild].getKey() <=
				m_elements[rightChild].getKey())
				maxChild = rightChild;
			else
				maxChild = leftChild;
		}
		if (m_elements[root].getKey() <
			m_elements[maxChild].getKey())
		{
			swap(m_elements[root], m_elements[maxChild]);
			ReHeapDown(maxChild, bottom);
		}
	}
}

void Heap::ReHeapUp(int root, int bottom)
{
	int parent;
	if (bottom > root)
	{
		parent = (bottom - 1) / 2;
		if (m_elements[parent].getKey() <
			m_elements[bottom].getKey())
		{
			swap(m_elements[parent], m_elements[bottom]);
			ReHeapUp(root, parent);
		}
	}
}
void Heap::print()
{
	for (int i = 0; i < m_numElements; i++)
		cout << m_elements[i].getKey() << ", ";
}

void main()
{
	Heap *grades = new Heap(10);
	cout << "Building" << endl;
	grades->Enqueue(6);
	grades->Enqueue(5);
	grades->Enqueue(3);
	grades->Enqueue(1);
	grades->Enqueue(8);
	grades->Enqueue(7);
	grades->Enqueue(2);
	grades->Enqueue(4);

	cout << "printing" << endl;
	grades->print();

	cout << "sorting" << endl;
	HeapItem *temp;
	while ((temp = grades->Dequeue()) != nullptr)
	{
		cout << "Deleting " << temp->getKey() << endl;
		delete temp;
		cout << "Elements in the heap " << endl;
		grades->print();
		cout << endl;
	}
}