N-ary Min Heap

minheap.hpp

#ifndef MINHEAP_H
#define MINHEAP_H

#include <vector>
#include <utility>
#include <stdexcept>

template <class T>
class MinHeap {
public:
	MinHeap(int n);
	/* Constructor that builds a n-ary Min Heap
	   This should work for any d >= 2,
	   but doesn't have to do anything for smaller d.*/

	~MinHeap();

	void add(T item, int priority);
	/* adds the item to the heap, with the given priority. */

	const T & peek() const;
	/* returns the element with smallest priority.
	   Break ties however you wish.
	   Throws an exception if the heap is empty. */

	void remove();
	/* removes the element with smallest priority.
	   Break ties however you wish.
	   Throws an exception if the heap is empty. */

	bool isEmpty();
	/* returns true iff there are no elements on the heap. */

private:
	std::vector<std::pair<T,int>> items;
	int k;
};

template<typename T> 
MinHeap<T>::MinHeap(int n) {
	k = d;
}

template<typename T>
MinHeap<T>::~MinHeap() {
}

template<typename T>
void MinHeap<T>::add(T item, int priority) {
	//add item to vector
	items.push_back({ item,priority });
	
	//if vector size is 1, then only 1 item in array so nothing needs to be done
	if (items.size() == 1) return;

	//assuming more than 1 element, keep it sorted
	int currIndex = items.size() - 1;
	int parentIndex = (currIndex%k == 0) ? (currIndex - 1) / k : currIndex / k;
	while (items.at(currIndex).second < items.at(parentIndex).second) {
		//swap the two items
		auto temp = items.at(parentIndex);
		items.at(parentIndex) = items.at(currIndex);
		items.at(currIndex) = temp;

		//update indexes
		currIndex = parentIndex;
		parentIndex = (currIndex%k == 0) ? (currIndex - 1) / k : currIndex / k;
	}
}

template<typename T>
void MinHeap<T>::remove() {
	if (items.empty()) throw std::out_of_range("Heap Empty!");

	//Swap first item with the last and then pop it out
	items.at(0) = items.at(items.size() - 1);
	items.pop_back();

	//go down the heap and swap with lowest child (reverse add)
	bool hasSmallerChild = true;
	int currIndex = 0;
	int lowestIndex;
	do {
		//look for lowest index child
		lowestIndex = currIndex;
		for (int i = 1; i <= k; i++) {  //go through all children
			int childIndex = (currIndex * k) + i; //potential child index
			if (childIndex < (int)items.size()) { //if valid index
				if (items.at(childIndex).second < items.at(lowestIndex).second) {
					lowestIndex = childIndex;//if smaller, set that as smallest child
				}
			}
		}
		if (lowestIndex != currIndex) {
			//if there's a smaller child, swap the two
			auto temp = items.at(currIndex);
			items.at(currIndex) = items.at(lowestIndex);
			items.at(lowestIndex) = temp;
			currIndex = lowestIndex;
		}
		else hasSmallerChild = false;
	} while (hasSmallerChild);
}

template<typename T>
const T & MinHeap<T>::peek() const {
	if (items.empty()) throw std::out_of_range("Heap Empty!");
	return items.at(0).first;
}

template<typename T>
bool MinHeap<T>::isEmpty() {
	return items.empty();
}
#endif