C++ Heap Data Structure

Using Big O notation, add and remove data while sorting it at O(log(n)) speed which is very efficient. For best performance choose a forward or backward data order before adding data.

Written in C++ using templates.

#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <ctime>
using namespace std;

#define DEFAULT_SIZE 1000

unsigned int LeftChildIndex(const unsigned int index)
{
	return 2 * index + 1;
}

unsigned int RightChildIndex(const unsigned int index)
{
	return 2 * index + 2;
}

unsigned int ParentIndex(const int index)
{
	return (index - 1) / 2;
}

template <class TData> class HeapDataMembers
{
public:
	TData **items;
	unsigned int length, max;
	bool forward;
	HeapDataMembers() : max(DEFAULT_SIZE), length(0), forward(true)
	{
		items = new TData*[max];
		for (int i = 0; i < max; items[i++] = nullptr);
	}
	HeapDataMembers(unsigned int arraySize) : max(arraySize), length(0), forward(true)
	{
		if (max == 0)
			max = DEFAULT_SIZE;
		items = new TData*[max];
		for (int i = 0; i < max; items[i++] = nullptr);
	}
	~HeapDataMembers()
	{
		DeleteLength();
		if (items)
		{
			delete[]items;
			items = nullptr; // clean up the memory
		}
	}
	void DeleteLength()
	{
		if (items)
		{
			for (int i = 0; i < length; i++)
			{
				delete items[i];
				items[i] = nullptr; // clean up the memory
			}
		}
		length = 0;
	}
};

template <class TData> class Heap
{
private:
	HeapDataMembers<TData> *dm;
	void Rebuild(const unsigned int index);
public:
	Heap() : dm(new HeapDataMembers<TData>()) {}
	Heap(unsigned int arraySize) : dm(new HeapDataMembers<TData>(arraySize)) {}
	Heap(const Heap<TData> &obj);
	~Heap() { delete dm; }
	const Heap<TData> &operator=(const Heap<TData> &obj);
	unsigned int Length() const; // returns 0 when empty
	void MakeForward();
	void MakeBackward();
	void Add(const TData &data);
	bool Pop(TData &data); // returns false when there is no data
	void Clear();
};

template <class TData> Heap<TData>::Heap(const Heap<TData> &obj) : dm(new HeapDataMembers<TData>(1))
{
	this->operator=(obj);
}

template <class TData> const Heap<TData> &Heap<TData>::operator=(const Heap<TData> &obj)
{
	if (this != &obj)
	{
		Clear();
		dm->max = obj.dm->max;
		dm->length = obj.dm->length;
		dm->forward = obj.dm->forward;
		if (dm->items)
			delete[]dm->items;
		dm->items = new TData*[dm->max];
		int i;
		for (i = 0; i < dm->length; i++)
		{
			dm->items[i] = new TData;
			*(dm->items[i]) = *(obj.dm->items[i]);
		}
		for (; i < dm->max; dm->items[i++] = nullptr);
	}
	return (*this);
}

template <class TData> void Heap<TData>::Add(const TData &data)
{
	if (dm->length == dm->max) // then increase size of array
	{
		dm->max <<= 1;
		TData **newArray = new TData*[dm->max];
		int i;
		for (i = 0; i < dm->length; newArray[i++] = dm->items[i]);
		for (; i < dm->max; newArray[i++] = nullptr);
		for (i = 0; i < dm->length; dm->items[i++] = nullptr);
		delete[]dm->items;
		dm->items = newArray;
	}
	dm->items[dm->length] = new TData;
	*(dm->items[dm->length]) = data;
	unsigned int newidx = dm->length;
	while (newidx >= 0)
	{
		unsigned int parentidx = ParentIndex(newidx);
		if (dm->forward)
		{
			if (*dm->items[newidx] >= *dm->items[parentidx])
				break;
		}
		else
		{
			if (*dm->items[newidx] <= *dm->items[parentidx])
				break;
		}
		TData *temp = dm->items[newidx];
		dm->items[newidx] = dm->items[parentidx];
		dm->items[parentidx] = temp;
		newidx = parentidx;
	}
	dm->length++;
}

template <class TData> void Heap<TData>::Rebuild(const unsigned int index)
{
	const unsigned int leftidx = LeftChildIndex(index);
	if (leftidx < dm->length)
	{
		const unsigned int rightidx = RightChildIndex(index);
		unsigned int largeridx = rightidx; // this is an assumption
		if (dm->forward)
		{
			if ((largeridx >= dm->length) || (*dm->items[leftidx] < *dm->items[rightidx])) // then assumption was wrong
				largeridx = leftidx;
			if (*dm->items[index] > *dm->items[largeridx])
			{
				// swap data
				TData *temp = dm->items[index];
				dm->items[index] = dm->items[largeridx];
				dm->items[largeridx] = temp;
				Rebuild(largeridx); // Transform the semiheap rooted at largeridx into a heap
			}
		}
		else
		{
			if ((largeridx >= dm->length) || (*dm->items[leftidx] > *dm->items[rightidx])) // then assumption was wrong
				largeridx = leftidx;
			if (*dm->items[index] < *dm->items[largeridx])
			{
				// swap data
				TData *temp = dm->items[index];
				dm->items[index] = dm->items[largeridx];
				dm->items[largeridx] = temp;
				Rebuild(largeridx); // Transform the semiheap rooted at largeridx into a heap
			}
		}
	}
}

template <class TData> bool Heap<TData>::Pop(TData &data)
{
	if (dm->length)
	{
		data = *dm->items[0];
		delete dm->items[0];
		dm->length--;
		dm->items[0] = (dm->length ? dm->items[dm->length] : nullptr);
		dm->items[dm->length] = nullptr;
		if (dm->length > 1)
			Rebuild(0);
		return true;
	}
	return false;
}

template <class TData> unsigned int Heap<TData>::Length() const
{
	return dm->length;
}

template <class TData> void Heap<TData>::MakeForward()
{
	if (!dm->forward)
	{
		dm->forward = true;
		for (int index = dm->length / 2 - 1; index >= 0; index--)
			Rebuild(index);
	}
}

template <class TData> void Heap<TData>::MakeBackward()
{
	if (dm->forward)
	{
		dm->forward = false;
		for (int index = dm->length / 2 - 1; index >= 0; index--)
			Rebuild(index);
	}
}

template <class TData> void Heap<TData>::Clear()
{
	dm->DeleteLength();
}

int main()
{
	{
		Heap<int> h(3);
		int n = time(0);
		srand(n);
		for (int i = 0; i < 20; i++)
		{
			n = rand();
			cout << n << endl;
			h.Add(n);
		}
		h.MakeForward();
		cout << endl;
		while (h.Pop(n))
			cout << n << endl;
	}
	cout << endl;
	{
		Heap<string> h(3);
		string s;
		h.MakeBackward();
		for (int i = 0; i < 20; i++)
		{
			char c[4] = { 0,0,0,0 };
			c[0] = c[1] = c[2] = (char)(rand() % 26) + 97;
			s = c;
			cout << s << endl;
			h.Add(s);
		}
		cout << endl;
		while (h.Pop(s))
			cout << s << endl;
	}
	return 0;
}