数值类型的堆实现

Question

我正在努力提高代码的质量，并试图研究Heap数据结构。我已经实现了一个minHeap (堆中最小值节点具有更高的优先级)。参考文献：link1，link2，link3。这是注释的代码：

#include <iostream>
#include <vector>
#include <limits>

// Class for throwing `out of range` exceptions
class OutofRange
{
    std::string error = "The index is out of range.";
public:
    OutofRange()
    {

    }
    std::string what()
    {
        return error;
    }
};

// Class for MinHeap. The `arr` holds the heap elements. The `capacity` indicates total
// allocated space for the heap. The `length` indicates size of the heap.
template<typename T>
class MinHeap
{
    T* arr;
    size_t capacity;
    size_t length;
public:
    MinHeap(size_t);
    T get_min();
    void heapify(int);
    void insert(T);
    T delete_min();
    T delete_by_index(int);
    void print_heap();
};

// Constructor for the heap
template<typename T>
MinHeap<T>::MinHeap(size_t n)
{
    arr = new T[n];
    capacity = n;
    length = 0;
}

// Return the minimum node (root)
template<typename T>
T MinHeap<T>::get_min()
{
    if(length > 0)
    {
        return arr[0];
    }
    else
    {
        std::cout << "Error: Invalid access" << std::endl;
        throw OutofRange{};
    }
}

// Function to put a node at the right position if it has the possibility to move up
// in the heap
template<typename T>
void MinHeap<T>::heapify(int start)
{
    for(int i = start; i > 0; i = (i - 1) / 2)
    {
        if(arr[i] < arr[(i - 1) / 2])
        {
            std::swap(arr[i], arr[(i - 1) / 2]);
        }
        else
        {
            return;
        }
    }

}

// Inserts nodes to heap
template<typename T>
void MinHeap<T>::insert(T data)
{
    // Check if capacity is reached
    if(length == capacity)
    {
        std::cout << "Error: Heap capacity reached" << std::endl;
        return;
    }

    // Insert the node
    arr[length] = data;
    this -> heapify(length);
    length++;
}

// Deletes the minimum value node (root)
template<typename T>
T MinHeap<T>::delete_min()
{
    // Check if heap has any elements/ nodes
    if(length == 0)
    {
        std::cout << "Error: Invalid Access" << std::endl;
        throw OutofRange{};
    }

    // Replace minimum node (root) with the last node
    T del_min = arr[0];
    std::swap(arr[0], arr[length - 1]);
    arr[length - 1] = (T)NULL;
    length--;
    // Bring the new root to correct position based on value
    for(size_t i = 0; i < length - 1 && length > 0;)
    {
        int min_child;
        if(2 * i + 1 > length - 1)
        {
            break;
        }
        if(2 * i + 2 > length - 1)
        {
            min_child = 2 * i + 1;
        }
        else
        {
            min_child = arr[2 * i + 1] <= arr[2 * i + 2] ? 2 * i + 1 : 2 * i + 2;
        }
        if(arr[i] > arr[min_child])
        {
            std::swap(arr[i], arr[min_child]);
        }
        i = min_child;
    }
    return del_min;
}

// Deletes a node by index
template<typename T>
T MinHeap<T>::delete_by_index(int index)
{
    int del_val = arr[index];
    T min_val = std::numeric_limits<T>::min();
    arr[index] = min_val;
    this -> heapify(index);
    this -> delete_min();
    return del_val;
}

// Print the heap
template<typename T>
void MinHeap<T>::print_heap()
{
    std::cout << "The Min Heap: " << std::endl;
    if(length == 0)
    {
        std::cout << "Empty" << std::endl;
    }
    for(size_t i = 0; i < length; i++)
    {
        std::cout << arr[i] << "\t";
    }
    std::cout << std::endl;
}

int main()
{
    try
    {
        MinHeap<int> h1{10};
        int del_val;
        std::vector<int> input = {35, 33, 42, 10, 14, 19, 27, 44, 26, 31};
        // Insert input values to the heap
        for(size_t i = 0; i < input.size(); i++)
        {
            h1.insert(input[i]);
            h1.print_heap();
        }

        // Check if minimum value/ highest priority can be accessed
        std::cout << "Current Root: " << h1.get_min() << std::endl;

        // Delete by index test case
        del_val = h1.delete_by_index(2);
        std::cout << "Delete by index: " << del_val << std::endl;
        h1.print_heap();

        // Delete the minimum value
        for(size_t i = 0; i < input.size(); i++)
        {
            del_val = h1.delete_min();
            std::cout << "Deleted value: " << del_val << std::endl;
            h1.print_heap();
        }

        // Uncomment to test exception in deletion if delete_by_index test case is not present.
        //del_val = h1.delete_min();
        //std::cout << "Deleted value: " << del_val << std::endl;

        // Uncomment to test exception in accessing minimum value(root)
        //h1.get_min();
    }
    // Catch the out of range exceptions
    catch(OutofRange& e)
    {
        std::cout << e.what() << std::endl;
    }
    return 0;
}

1. 堆是否用于数值以外的数据类型？尽管我的实现使用模板，但它确实依赖于numeric_limits。假设数据类型不是数值型，它可以转换为如下所示的自定义数据类型: struct custom_type {T val；int优先级；custom_type(T，int p) { val = v；优先级= p；} //重载用于使用优先级字段的比较运算符。/*
2. 是否有更好的方法来处理out of range错误而不使用异常并且不返回INT_MAX、INT_MIN或0之类的值？
3. 在代码中还有哪些其他可能的改进？

Answer 1

霍夫曼的绝妙回答的增编(请先阅读并投票！)：

• 更喜欢初始化成员，而不是在构造期间分配成员: template MinHeap::MinHeap(size_t n)：arr{新TN}、容量{n}、长度{0}{}(这更清楚)，并且允许编译器警告(如-Weffc++ )，让您知道是否遗漏任何成员。
• 考虑提供一个接受std::initializer_list的构造函数，它比一次添加一个元素要高效得多: template MinHeap::MinHeap(std::initializer_list值)：MinHeap(values.size()) { std::copy(values.begin()，values.end()，arr)；length = values.size()；heapify(0)；}
• std::size_t总是拼写错误。或者添加using std::size_t;，或者(更好的，对于一个标头)完整地、完整地写它。
• get_min()和print_heap()不应该修改堆，所以声明它们为const。
• 没有必要使用this->显式限定对其他成员的调用--这只是不必要的混乱。
• 如果必须打印错误消息，则将它们写入错误流，而不是将它们混合到输出: catch(OutofRange& e) { std::cerr << e.what() << std::endl；}中。
• delete_by_index在这一行中将一个T分配给int：int del_val = arr索引；看起来它应该是const T del_val = arr索引；或者可能只是const autodel_val= arr索引；而且，这个函数接受它的索引为int，其中std::size_t更合适--这也是heapify的情况。
• 一旦delete_by_index()被固定为不需要std::numeric_limits，那么T就不再被限制为算术类型，我们应该能够使用任何类型的<操作符(例如std::string)作为值类型。事实上，一旦修复了其他小错误，测试程序(不使用delete_by_index())就会与std::string一起工作。
• 在测试程序中，让我们让input成为一个const值，并使用基于范围的for来迭代它: auto = {"35“、"33”、"42“、"10”、"14“、"19”、"27“、"44”、"26“、"31"}；//将输入值插入堆(auto & i: input) { h1.insert(i)；h1.print_heap()；} //删除(auto & i: input) { del_val = h1.delete_min()；std::clog <<“已删除值：”<< del_val << std::endl；h1.print_heap()；
• 最后，考虑使用单元测试框架来执行代码，并检查是否产生了正确的结果或异常。正确的操作，可以提供一个更完整的测试套件，从而使重构能够以更高的信心完成，从而避免引入新的bug。而且，您也不必检查大量的输出，以确保测试已经通过。