NaryHeap as a generalization of binary heap. Each node has up to N children. A template specialization for N = 2 (BinaryHeap) is given too. Though apparently not standard, I've also defined removing a node other than the root, and removing a node by value.
#include <iostream>
#include <functional>
#include <algorithm>
#include <array>
template <std::size_t N, typename T = int, typename Comparator = std::less<T>>
class NaryHeap {
T* data;
std::size_t heapSize, arraySize;
const Comparator comparator;
public:
NaryHeap (std::size_t size) : data(new T[size]), heapSize(0), arraySize(size), comparator(Comparator{}) {}
~NaryHeap() {delete[] data;}
bool empty() const {return heapSize == 0;}
T getMinimum() const {if (empty()) throw std::string("getMinimum() is invalid because the heap is empty."); else return data[0];}
void insert (const T& value);
template <typename... Args> void insert (Args&&...);
void removeMin() {removeHelper(0);}
void remove (std::size_t nodeIndex) {removeHelper(nodeIndex);}
void removeByValue (const T&);
void print() const;
private:
std::size_t getChildIndex (std::size_t n, std::size_t nodeIndex) const {return N * nodeIndex + n + 1;} // The index of the nth child of the node with index 'nodeIndex'. n takes on values from 0 to N-1.
std::size_t getLeftChildIndex (std::size_t nodeIndex) const {return getChildIndex(0, nodeIndex);} // The leftmost child.
std::size_t getRightmostChildIndex (std::size_t nodeIndex) const {return std::min (heapSize - 1, getChildIndex(N-1, nodeIndex));} // The rightmost child.
std::size_t getParentIndex (std::size_t nodeIndex) const {return (nodeIndex - 1) / N;} // This rounds down if nodeIndex - 1 is not a multiple of N. Hence the returned value is the same regardless of which child the node is of the parent.
void heapifyUp (std::size_t nodeIndex);
void heapifyDown (std::size_t nodeIndex);
void removeHelper (std::size_t nodeIndex);
bool isRoot (std::size_t nodeIndex) const {return nodeIndex == 0;}
};
template <std::size_t N, typename T, typename Comparator>
void NaryHeap<N, T, Comparator>::insert (const T& value) {
if (heapSize == arraySize)
throw std::string ("Heap's underlying storage is at maxiumum capacity. Cannot insert.");
data[heapSize] = value;
heapifyUp(heapSize);
heapSize++;
}
template <std::size_t N, typename T, typename Comparator>
void NaryHeap<N, T, Comparator>::heapifyUp (std::size_t nodeIndex) { // Recursively swap with parent node until the parent node's value is less than the node's value, or until the node has become the root of the heap.
if (isRoot(nodeIndex))
return;
const std::size_t parentIndex = getParentIndex(nodeIndex);
if (comparator(data[nodeIndex], data[parentIndex])) {
std::swap (data[nodeIndex], data[parentIndex]); // Or 'const T temp = data[parentIndex]; data[parentIndex] = data[nodeIndex]; data[nodeIndex] = temp;' if swapping without using the algorithm library.
heapifyUp(parentIndex);
}
}
template <std::size_t N, typename T, typename Comparator>
template <typename... Args>
void NaryHeap<N, T, Comparator>::insert (Args&&... args) {
const T a[] = {std::forward<Args>(args)...};
for (std::size_t i = 0; i < sizeof...(Args); i++)
insert(a[i]);
}
template <std::size_t N, typename T, typename Comparator>
void NaryHeap<N, T, Comparator>::removeHelper (std::size_t nodeIndex) {
if (empty())
throw std::string ("Cannot remove, because the heap is empty.");
data[nodeIndex] = data[heapSize - 1];
heapSize--;
if (heapSize > 0)
heapifyDown(nodeIndex);
}
template <std::size_t N, typename T, typename Comparator>
void NaryHeap<N, T, Comparator>::heapifyDown (std::size_t nodeIndex) { // Recursively swap with the child node that has the smaller value until the parent child's value is less than the node's value, or until the node has no children.
const std::size_t leftChildIndex = getLeftChildIndex(nodeIndex);
if (leftChildIndex >= heapSize)
return; // There are no children, so heapifyDown ends.
const std::size_t childIndex = [=]() { // Seeking the index among all the children of the node at position nodeIndex with the small T value.
std::size_t index = leftChildIndex;
T minValue = data[leftChildIndex];
const std::size_t rightmostChildIndex = getRightmostChildIndex(nodeIndex);
for (std::size_t i = leftChildIndex + 1; i < rightmostChildIndex; i++)
if (comparator(data[i], minValue)) {
index = i;
minValue = data[i];
}
return index;
}();
// Below is another way of getting 'childIndex' (tested). But on top of requiring '#include <vector>', building the 'indices' vector is adds to the time complexity.
// const std::size_t rightmostChildIndex = getRightmostChildIndex(nodeIndex), K = rightmostChildIndex - leftChildIndex + 1;
// std::vector<std::size_t> indices(K);
// for (std::size_t i = 0; i < K; i++)
// indices[i] = i + leftChildIndex;
// const std::size_t childIndex = *std::min_element (indices.begin(), indices.end(), [this](std::size_t x, std::size_t y) {return comparator(data[x], data[y]);});
if (comparator(data[nodeIndex], data[childIndex]))
return;
std::swap (data[childIndex], data[nodeIndex]);
heapifyDown(childIndex);
}
template <std::size_t N, typename T, typename Comparator>
void NaryHeap<N, T, Comparator>::removeByValue (const T& t) {
const int nodeIndex = [this, &t]() {
for (int i = 0; i < (int)heapSize; i++)
if (data[i] == t)
return i;
return -1; // i.e. not found.
}();
if (nodeIndex == -1)
return;
remove(nodeIndex);
}
template <std::size_t N, typename T, typename Comparator>
void NaryHeap<N, T, Comparator>::print() const {
for (std::size_t i = 0; i < heapSize; i++)
std::cout << data[i] << ' ';
std::cout << '\n';
}
template <typename T, typename Comparator>
using BinaryHeap = NaryHeap<2, T, Comparator>;
// Testing
int main() {
// A binary heap as a special case.
BinaryHeap<int, std::greater<int>> binaryHeap(10); // A max binary heap due to std::greater<int>.
binaryHeap.insert(5);
binaryHeap.insert(3,1,6,0,8,2,9,4,7);
binaryHeap.print(); // 9 8 6 5 7 1 2 3 4 0
binaryHeap.removeMin();
binaryHeap.print(); // 8 7 6 5 0 1 2 3 4
binaryHeap.removeMin();
binaryHeap.print(); // 7 5 6 4 0 1 2 3
binaryHeap.remove(5); // Removes the node in the 5th position (i.e. removes the node with value 1).
binaryHeap.print(); // 7 5 6 4 0 3 2
binaryHeap.removeByValue(3);
binaryHeap.print(); // 7 5 6 4 0 2
// A ternary heap.
struct CompareCharacters {
bool operator()(char x, char y) const {return (int)x < (int)y;}
};
NaryHeap<3, char, CompareCharacters> ternaryHeap(10); // The default std::less<char> does the same thing as CompareCharacters actually.
ternaryHeap.insert('b','c','e','a','g','d','j','i','h');
ternaryHeap.print(); // a c e b g d j i h (the 3 children of a are c,e,b, and the 3 children of c are g,d,j, and the 2 children of e are i,h).
ternaryHeap.removeMin();
ternaryHeap.print(); // c d e b g h j i
ternaryHeap.remove(4);
ternaryHeap.print(); // c d e b i h j
ternaryHeap.removeByValue('i');
ternaryHeap.print(); // c d e b j h
}
Copy and move constructors (tested):
template <std::size_t N, typename T, typename Comparator>
NaryHeap<N, T, Comparator>::NaryHeap (const NaryHeap& other) : data(new T[other.arraySize]),
heapSize(other.heapSize), arraySize(other.arraySize), comparator(other.comparator) {
for (std::size_t i = 0; i < heapSize; i++)
data[i] = other.data[i];
}
template <std::size_t N, typename T, typename Comparator>
NaryHeap<N, T, Comparator>::NaryHeap (NaryHeap&& other) : data(other.data),
heapSize(other.heapSize), arraySize(other.arraySize), comparator(other.comparator) {
other.data = nullptr;
other.heapSize = 0;
other.arraySize = 0;
}
template <std::size_t N, typename T, typename Comparator>
NaryHeap<N, T, Comparator>& NaryHeap<N, T, Comparator>::operator= (const NaryHeap& other) {
if (other == *this)
return *this;
data = new T[other.arraySize];
heapSize = other.heapSize;
arraySize = other.arraySize;
comparator = other.comparator;
for (std::size_t i = 0; i < heapSize; i++)
data[i] = other.data[i];
return *this;
}
template <std::size_t N, typename T, typename Comparator>
NaryHeap<N, T, Comparator>& NaryHeap<N, T, Comparator>::operator= (NaryHeap&& other) {
if (other == *this)
return *this;
data = other.data;
heapSize = other.heapSize;
arraySize = other.arraySize;
comparator = other.comparator;
other.data = nullptr;
other.heapSize = 0;
other.arraySize = 0;
return *this;
}
Due to the problem mentioned by Hurkyl, I propose the following change for removing an arbitrary node:
template <std::size_t N, typename T, typename Comparator>
void NaryHeap<N, T, Comparator>::remove (std::size_t nodeIndex) {
removeHelper(nodeIndex, getMaxNodeIndex());
}
template <std::size_t N, typename T, typename Comparator>
std::size_t NaryHeap<N, T, Comparator>::indexOfFirstChildlessNode() const {
// The following is a O(N) search. A O(logN) search should exist and will be sought later.
for (std::size_t i = 0; i < heapSize; i++)
if (getLeftChildIndex(i) >= heapSize)
return i;
return heapSize - 1;
}
template <std::size_t N, typename T, typename Comparator>
std::size_t NaryHeap<N, T, Comparator>::getMaxNodeIndex() const {
if (empty())
throw std::string("getMinimum() is invalid because the heap is empty.");
// The node with the largest value (using comparator) must be a node with no child, since the children of a node, by definition of heap, will have values larger than that node.
const std::size_t firstIndex = indexOfFirstChildlessNode();
std::size_t maxNodeIndex = firstIndex;
T largestValue = data[firstIndex];
for (std::size_t i = firstIndex + 1; i < heapSize; i++) {
if (comparator(largestValue, data[i])) {
largestValue = data[i];
maxNodeIndex = i;
}
}
return maxNodeIndex;
}
template <std::size_t N, typename T, typename Comparator>
void NaryHeap<N, T, Comparator>::removeHelper (std::size_t nodeIndex, std::size_t lastNodeIndex) { // lastNodeIndex = heapSize - 1 by default.
if (empty())
throw std::string ("Cannot remove, because the heap is empty.");
data[nodeIndex] = data[lastNodeIndex];
heapSize--;
heapifyDown(nodeIndex);
}
My entire revised code with the above changes can be found here.
So far, I've found no error with arbitrary removals using this new version of remove, so I will attempt a mathematical proof now. If I don't end up providing one, then it means that either I don't know how to prove the correctness, or that the remove function is simply not correct.
increase-keyshould apply to removing an arbitrary node too. \$\endgroup\$