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 min or max heap 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 minheap;
	HeapDataMembers();
	HeapDataMembers(unsigned int arraySize);
	~HeapDataMembers();
	void DeleteLength();
};

template <class TData> class Heap
{
private:
	HeapDataMembers<TData> *dm;
	void RebuildMinHeap(const unsigned int index);
	void RebuildMaxHeap(const unsigned int index);
public:
	Heap();
	Heap(unsigned int 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 MakeMinHeap(); // default is a min heap
	void MakeMaxHeap();
	void Add(const TData &data);
	bool Pop(TData &data); // returns false when there is no data
	const TData *Peek(); // peek at the data on the heap without popping it off
	void Clear();
};

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


template <class TData> Heap<TData>::Heap()
{
	dm = new HeapDataMembers<TData>();
}

template <class TData> Heap<TData>::Heap(unsigned int arraySize)
{
	dm = new HeapDataMembers<TData>(arraySize);
}

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->minheap = obj.dm->minheap;
		if (dm->items)
			delete[]dm->items;
		dm->items = new TData*[dm->max];
		unsigned 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];
		unsigned int i;
		for (i = 0; i < dm->length; i++)
			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;
	if (dm->minheap)
	{
		while (newidx >= 0)
		{
			unsigned int parentidx = ParentIndex(newidx);
			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;
		}
	}
	else
	{
		while (newidx >= 0)
		{
			unsigned int parentidx = ParentIndex(newidx);
			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>::RebuildMinHeap(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 ((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;
			RebuildMinHeap(largeridx); // Transform the semiheap rooted at largeridx into a heap
		}
	}
}

template <class TData> void Heap<TData>::RebuildMaxHeap(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 ((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;
			RebuildMaxHeap(largeridx); // Transform the semiheap rooted at largeridx into a heap
		}
	}
}

template <class TData> const TData *Heap<TData>::Peek()
{
	if (dm->length)
		return dm->items[0];
	return nullptr;
}

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)
		{
			if(dm->minheap)
				RebuildMinHeap(0);
			else
				RebuildMaxHeap(0);
		}
		return true;
	}
	return false;
}

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

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

template <class TData> void Heap<TData>::MakeMaxHeap()
{
	if (dm->minheap)
	{
		dm->minheap = false;
		for (int index = dm->length / 2 - 1; index >= 0; index--)
			RebuildMaxHeap(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);
		}
		cout << endl;
		while (h.Pop(n))
			cout << n << endl;
	}
	cout << endl;
	{
		Heap<string> h(3);
		string s;
		h.MakeMaxHeap();
		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;
}

Comment