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