C++ Data Structures with Templates

The Code

MinHeap.h as standard C++ class

#include <stdint.h>
template <class T> inline void swap(T& a, T& b)
{
	T c(a); a = b; b = c;
};
class MinHeap {
public:
	MinHeap(size_t); 
	int16_t getMin();
	int16_t extractMin();
	bool insert(int16_t);
	size_t indexOf(int16_t);
	void decreaseKey(size_t, int16_t);
	void deletekey(size_t);
private:
	int16_t* mHeap; // pointer to the array
	size_t capacity;
	size_t currentSize;
	void heapify(size_t);
	size_t left(size_t);
	size_t right(size_t);
	size_t parent(size_t);
};
// constructor
MinHeap::MinHeap(size_t maxSize) {
	capacity = maxSize;
	currentSize = 0;
	mHeap = new int16_t[capacity];
}
// public methods
int16_t MinHeap::getMin() {
	return mHeap[0];
}
int16_t MinHeap::extractMin() {
	// returns and removes min value
	switch (currentSize) {
	case 0:
		// how do we flag an error?
		return INT16_MAX; // maybe as this is a Min Heap
	case 1:
		return mHeap[--currentSize];
	default:
	{ // {} needed for variable definition
		int16_t retVal = mHeap[0];
		mHeap[0] = mHeap[--currentSize];
		heapify(0);
		return retVal;
	}
	}
}
bool MinHeap::insert(int16_t nVal) {
	if (currentSize == capacity) {
		return false;
	}
	mHeap[currentSize] = nVal; // stores the new value
														 // we now need to ensure that the new value is in the
														 // right place where the parent is a lower value
	size_t i = currentSize;
	while (i != 0 && mHeap[parent(i)] > mHeap[i]) {
		swap<int16_t>(mHeap[parent(i)], mHeap[i]);
		i = parent(i);
	}
	currentSize++;
	return true;
}
size_t MinHeap::indexOf(int16_t find) {
	// this is not an efficient feature O(n) worst case
	for (size_t i = 0; i < currentSize; i++) {
		if (mHeap[i] == find) {
			return i;
		}
	}
	return SIZE_MAX; // clue that it was not found
}
void MinHeap::decreaseKey(size_t index, int16_t newVal) {
	mHeap[index] = newVal;
	while (index != 0 && mHeap[parent(index)] > mHeap[index])
	{
		swap<int16_t>(mHeap[parent(index)], mHeap[index]);
		index = parent(index);
	}
}
void MinHeap::deletekey(size_t index) {
	decreaseKey(index, INT16_MIN); // bug if not out of the heap range
	extractMin(); // zap it
}
// Private Methods
void MinHeap::heapify(size_t index) {
	size_t leftChild = left(index);
	size_t rightChild = right(index);
	size_t min = index;
	if (leftChild < currentSize && mHeap[leftChild] < mHeap[index]) {
		min = leftChild;
	}
	if (rightChild < currentSize && mHeap[rightChild] < mHeap[min]) {
		min = rightChild;
	}
	if (min != index) {
		swap<int16_t>(mHeap[index], mHeap[min]);
		heapify(min); // recursive call
	}
}
size_t MinHeap::left(size_t index) {
	return 2 * index + 1;
}
size_t MinHeap::right(size_t index) {
	return 2 * index + 2;
}
size_t MinHeap::parent(size_t index) {
	return (index - 1) / 2;
}

MinHeap.cpp

#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include <iostream>
//using namespace std;
#include "MinHeap.h"
int16_t ints[] = { 3, 7, 2, 9, 17, 82, 99, 15, 14, 1, 8 };
int main()
{
	MinHeap mHeap(20);
	for (int i = 0; i < 11; i++) {
		mHeap.insert(ints[i]);
	}
	std::cout << "Lowest heap key is: " << mHeap.getMin() << '\n';
	for (int i = 0; i < 5; i++) {
		std::cout << "Extracted: " << mHeap.extractMin() << '\n';
	}
	std::cout << "Lowest heap key now: " << mHeap.getMin() << '\n';
	size_t f = mHeap.indexOf(15);
	mHeap.decreaseKey(f, 8);
	std::cout << "Lowest heap key now: " << mHeap.getMin() << '\n';
	std::cin.get();
	return 0;
}

QueueItem.h

class QueueItem {
public:
	uint8_t priority;
	uint8_t action;
	QueueItem(uint8_t priority, uint8_t action) {
		this->priority = priority;
		this->action = action;
	}
	QueueItem() {
		priority = action = UINT8_MAX;
	}
	// note my == is based on action
	bool operator==(const QueueItem a) {
		return(this->action == a.action);
	};
	// < and > are based on the priority
	// as that is the key
	bool operator<(const QueueItem a) {
		return(this->priority < a.priority);
	}
	bool operator>(const QueueItem a) {
		return(this->priority > a.priority);
	}
};

PriorityQueue.h

template <class T> inline void swap(T& a, T& b)
{
	T c(a); a = b; b = c;
};
// Note to Self you can delete an item by increasing priority to 0 and then popping it
// assuming that top priority is 1 and not zero
template<typename T>
class PriorityQueue {
public:
	PriorityQueue(size_t);
	~PriorityQueue();
	T top();
	bool empty();
	size_t size();
	bool push(T);
	T pop();
	size_t getIndex(T);
	bool increasePriority(size_t, T);
private:
	T* mHeap; // pointer to the array
	size_t capacity;
	size_t currentSize;
	void heapify(size_t);
	size_t left(size_t);
	size_t right(size_t);
	size_t parent(size_t);
};
// constructor and destructor
template<typename T>
PriorityQueue<T>::PriorityQueue(size_t maxSize) {
	capacity = maxSize;
	currentSize = 0;
	mHeap = new T[maxSize];
}
template<typename T>
PriorityQueue<T>::~PriorityQueue() {
	delete mHeap;
}
//public methods
template<typename T>
T PriorityQueue<T>::top() {
	return mHeap[0];
}
template<typename T>
bool PriorityQueue<T>::empty() {
	return currentSize == 0;
}
template<typename T>
size_t PriorityQueue<T>::size() {
	return currentSize;
}
template<typename T>
bool PriorityQueue<T>::push(T newItem) {
	if (currentSize == capacity) {
		return false;
	}
	mHeap[currentSize] = newItem;
	size_t i = currentSize;
	while (i != 0 && mHeap[parent(i)] > mHeap[i]) {
		swap<T>(mHeap[parent(i)], mHeap[i]);
		i = parent(i);
	}
	currentSize++;
	return true;
}
template<typename T>
T PriorityQueue<T>::pop() {
	switch (currentSize) {
	case 0:
		// error calling software should guard against this
		return *(new T());
	case 1:
		return mHeap[--currentSize];
	default:
	{
		T retVal = mHeap[0];
		mHeap[0] = mHeap[--currentSize];
		heapify(0);
		return retVal;
	}
	}
}
template<typename T>
size_t PriorityQueue<T>::getIndex(T item) {
	for (size_t i = 0; i < currentSize; i++) {
		if (mHeap[i] == item) {
			return i;
		}
	}
	return SIZE_MAX;
}
template<typename T>
bool PriorityQueue<T>::increasePriority(size_t index, T revItem) {
	if (index >= 0 && index < currentSize) {
		if (revItem < mHeap[index]) {
			mHeap[index] = revItem;
			while (index != 0 && mHeap[parent(index)] > mHeap[index])
			{
				swap<T>(mHeap[parent(index)], mHeap[index]);
				index = parent(index);
			}
			return true;
		}
	}
	return false;
}
// private methods
template<typename T>
void PriorityQueue<T>::heapify(size_t index) {
	size_t leftChild = left(index);
	size_t rightChild = right(index);
	size_t min = index;
	if (leftChild < currentSize && mHeap[leftChild] < mHeap[index]) {
		min = leftChild;
	}
	if (rightChild < currentSize && mHeap[rightChild] < mHeap[min]) {
		min = rightChild;
	}
	if (min != index) {
		swap<T>(mHeap[index], mHeap[min]);
		heapify(min);
	}
}
template<typename T>
size_t PriorityQueue<T>::left(size_t index) {
	return 2 * index + 1;
}
template<typename T>
size_t PriorityQueue<T>::right(size_t index) {
	return 2 * index + 2;
}
template<typename T>
size_t PriorityQueue<T>::parent(size_t index) {
	return (index - 1) / 2;
}

PriorityQueue.cpp

#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include <iostream>
#include "PriorityQueue.h"
#include "QueueItem.h"
int main()
{
	PriorityQueue<QueueItem> mQueue(20);
	QueueItem q(4, 5);
	mQueue.push(q);
	std::cout << "Queue size: " << mQueue.size() << '\n';
	QueueItem p = mQueue.top();
	std::cout << "Item priority: " << (int)p.priority << '\n';
	for (int i = 0; i < 10; i++) {
		QueueItem r(rand() % 19, rand() % 29);
		mQueue.push(r);
	}
	QueueItem x(9, 11);
	mQueue.push(x);
	std::cout << "Queue size now: " << mQueue.size() << '\n';
	size_t idx = mQueue.getIndex(x);
	x.priority = 3;
	mQueue.increasePriority(idx, x);
	for (; !mQueue.empty();) {
		p = mQueue.pop();
		std::cout << "Item priority: " << (int)p.priority << " Item action: " << (int)p.action << '\n';
	}
	std::cin.get();
    return 0;
}

PriorityQueue.ino

#include "PriorityQueue.h"
#include "QueueItem.h"
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
void setup() {
  Serial.begin(115200);
  PriorityQueue<QueueItem> mQueue(20);
  QueueItem q(4, 5);
  mQueue.push(q);
  Serial << "Queue size: " << mQueue.size() << '\n';
  QueueItem p = mQueue.top();
  Serial << "Item priority: " << (int)p.priority << '\n';
  for (int i = 0; i < 10; i++) {
    QueueItem r(random(1,19), random(1,29));
    mQueue.push(r);
  }
  QueueItem x(9, 11);
  mQueue.push(x);
  Serial << "Queue size now: " << mQueue.size() << '\n';
  size_t idx = mQueue.getIndex(x);
  x.priority = 3;
  mQueue.increasePriority(idx, x);
  for (; !mQueue.empty();) {
    p = mQueue.pop();
    Serial << "Item priority: " << (int)p.priority << " Item action: " << (int)p.action << '\n';
  }
}

Read the chapter in my book C++ Data Structures with immediate download from Amazon