Created
April 2, 2019 04:01
-
-
Save switchswap/2c5250002243a626d9e1f69ae15faf7a to your computer and use it in GitHub Desktop.
N-ary Min Heap
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment