3
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ When removing an arbitrary element, don't you have to consider both the possibility that it needs to go down and that it goes up? After all, you have no guarantee that the last element is the largest element. \$\endgroup\$
    – user14393
    Oct 19, 2015 at 17:15
  • \$\begingroup\$ Darn. You are right. So removing an arbitrary element other than the root is more complex than I thought. I will try to work that out. I think we just need to compare the value to the parent's value and if it is larger, sift down, and if it is smaller, sift up. But it might be more complex than that. Any cases where that won't work? \$\endgroup\$
    – prestokeys
    Oct 19, 2015 at 21:55
  • \$\begingroup\$ All I remember for sure is that the last time I thought on the issue, I gave up and decided it wasn't worth the effort. \$\endgroup\$
    – user14393
    Oct 19, 2015 at 21:58
  • \$\begingroup\$ This discussion on the increase-key should apply to removing an arbitrary node too. \$\endgroup\$
    – user14393
    Oct 19, 2015 at 22:01
  • \$\begingroup\$ What about searching through the children of the last parent, take the child with the largest node value, and swap the removed node with that child? Then sifting down will preserve the heap property, won't it? If true, I will have to come up with a mathematical proof though, which is not my forte. If false, I will be wasting my energy implementing it. \$\endgroup\$
    – prestokeys
    Oct 19, 2015 at 22:20

1 Answer 1

1
\$\begingroup\$

In this part of the heapifyDown function

if (comparator(data[nodeIndex], data[childIndex]))
        return;

This will be more appropriate because you should want to end recursion if they are equal.

if (!comparator(data[childIndex], data[nodeIndex]))
    return;

or

 if (comparator(data[childIndex], data[nodeIndex])) {
     std::swap (data[childIndex], data[nodeIndex]);
     heapifyDown(childIndex);
 }

Also instead of creating a lambda and calling it. It would be cleaner to separate this in a new function.

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;
    }();

This can be simplified :

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);
}

to this :

 template <std::size_t N, typename T, typename Comparator>
    void NaryHeap<N, T, Comparator>::removeByValue (const T& t) {

        for (int i = 0;  i < (int)heapSize;  i++) {
            if (data[i] == t) {
                remove(nodeIndex);
                break;
                // or just return remove(nodeIndex);

            }
        }
    }

In removeHelper

This is redundant

 if (heapSize > 0)
        heapifyDown(nodeIndex);

If heapSize is 0

this part in heapifyDown will take care of it.

if (leftChildIndex >= heapSize)
        return;

It would be more clear to use std::underflow_error and std::overflow_error under the <stdexcept> header.


Your comments are too unnecessary, let the code speak for itself.

\$\endgroup\$
4
  • \$\begingroup\$ @ MAG Thank you. I guess the perfect forwarding in insert (Args&&... args) is also unnecessary, since there is no good reason to keep any r-valueness in the heap, right? \$\endgroup\$
    – prestokeys
    Oct 19, 2015 at 2:37
  • \$\begingroup\$ Its fine, you could make the other insert overload private and just use std::move inside it. \$\endgroup\$
    – MAG
    Oct 19, 2015 at 2:51
  • \$\begingroup\$ Also using varadic templates may be a bit overkill it seams using std::initializer_list would be more appropriate. I could be wrong though. \$\endgroup\$
    – MAG
    Oct 19, 2015 at 3:01
  • \$\begingroup\$ @ MAG You might be interested in the point made by Hurkyl regarding removing an arbitrary node, and my proposed solution above to remedy that problem. Neither of us know yet if it is correct. \$\endgroup\$
    – prestokeys
    Oct 19, 2015 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.