N元堆实现

Question

NaryHeap作为二进制堆的推广。每个节点最多有N个子节点。给出了N=2 (BinaryHeap)的模板专门化。虽然显然不是标准的，但我也定义了删除根以外的节点，并按值删除节点。

#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
}

复制和移动构造函数(测试)：

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

由于Hurkyl提到的问题，我提议对删除任意节点进行以下更改：

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

我修改过的所有代码都可以找到这里。

到目前为止，我还没有发现使用这个新版本的remove任意删除的错误，所以现在我将尝试一个数学证明。如果我最后不提供一个，那么这意味着要么我不知道如何证明正确性，要么remove函数就是不正确的。

Answer 1

在heapifyDown函数的这一部分中

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

这样做更合适，因为如果递归相等，则应该终止递归。

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

或

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

也没有创建一个lambda并调用它。在一个新的功能中将这一点分开会更干净。

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

这可以简化如下：

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>::removeByValue (const T& t) {

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

            }
        }
    }

在removeHelper中

这是多余的

 if (heapSize > 0)
        heapifyDown(nodeIndex);

如果heapSize是0

heapifyDown中的这个部分会处理好它。

if (leftChildIndex >= heapSize)
        return;

在std::underflow_error头下使用std::overflow_error和<stdexcept>将更加清楚。

您的评论太不必要了，让代码本身来说明。