堆类实现

Question

     /*insert(int value)
     shift_up(i) - needed for insert
     get_max - returns the max item, without removing it
     get_size() - return number of elements stored
     is_empty() - returns true if heap contains no elements
     extract_max - returns the max item, removing it
     shift_down(i) - needed for extract_max
     remove(i) - removes item at index x
     heapify - create a heap from an array of elements, needed for 
     heap_sort
     heap_sort() - take an unsorted array and turn it into a sorted 
     array in-place using a max heap*/
    #include <vector>
    #include <iostream>
    #include <algorithm>
    #include <climits>
    using namespace std;
    class heap{
    public:
        heap();
        heap(const heap& other);
        heap& operator=(heap src);
        ~heap();
        int parent(int i);
        int right_child(int i);
        int left_child(int i);
        void insert(int value);
        void shift_up(int i);
        int get_max();
        int get_size();
        bool is_empty();
        int extract_max();
        void shift_down(int i);
        void remove(int i);
        void heapify(const vector<int>&); //Build array into a heap
        void heap_sort(const vector<int>&);
        void display();
    private:
        vector<int> v;
        int size;
    };
    // only constructer is needed as we are using a built in library so no destructor
    heap::heap():size(0),v({0}){}

    heap::heap(const heap& other){
        size = other.size;
        v = other.v;
    }

    heap& heap::operator=(heap src){
        swap(size, src.size);
        swap(v,src.v);
    }

    heap::~heap(){}

    int heap::parent(int i){
        return floor(i/2);
    }
    int heap::left_child(int i){
        return 2*i;
    }
    int heap::right_child(int i){
        return 2*i + 1;
    }
    void heap::insert(int value){
        v.push_back(value);
        size += 1;
        shift_up(size);
    }
    void heap::shift_up(int i){
        while (i > 1 && (v[parent(i)] < v[i])){
            swap(v[parent(i)], v[i]);
            i = parent(i);
        }
    }

    int heap::get_max(){
        return v[1];
    }

    int heap::get_size(){
        return size;
    }
    bool heap::is_empty(){
        bool k;
        (size>0)? k = true: k = false;
        return k;
    }
    int heap::extract_max(){

        int maxi = v[1];

        v[1] = v[size];

        size -= 1;

        shift_down(1);

        return maxi;
    }
    void heap::shift_down(int i){
        int maxIndex = i; 

        int l = left_child(i);

        if(l <= size && v[maxIndex] < v[l])
            maxIndex = l;

        int r = right_child(i);

        if(r <= size && v[maxIndex] < v[r])
            maxIndex = r;

        if (i != maxIndex){
            swap(v[i], v[maxIndex]);
            shift_down(maxIndex);
        }
    }
    void heap::remove(int value){
    int i = 0;
    int focus;
        while(i <= size){
            if(v.at(i) == value){
                focus = i;
                break;
            }
            i += 1;
        }
        v[focus] = INT_MAX;
        shift_up(focus);
        extract_max();
    }
    void heap::heapify(const vector<int>& A){
        v.resize(A.size()+1);
        size = A.size();
        int j = 1;
        for(auto x: A){
            v[j] = x;
            j++;
        }
        for(int i = parent(size) ; i >= 1 ; i--){  //running time n 
            shift_down(i);
        }
    }
    void heap::heap_sort(const vector<int> &A){
        heapify(A);

        while(size > 1){
            swap(v[1],v[size]);
            size -= 1;
            shift_down(1);
        }
    }
    void heap::display(){
        for(auto x: v)
            cout << x << " ";
    }

请提出可能的良好的代码管理技术，可以帮助我编写和维护更好的代码在未来。我认为实现和维护数据结构可能是如何为像我这样的初学者维护代码的一个很好的实践。

Answer 1

1. 对您的类型使用正确的数字域，例如unsigned而不是int表示大小，因为负值大小对任何数据结构都是无效的。它还简化了一些错误处理。
2. 标题中的using namespace是一个大的不-不。如果您想在代码中省略std::，就需要本地化它，比如在类声明中放置类型防御，或者让.cpp与.h分离。
3. is_empty可能还不如返回三元表达式，而不是使用临时bool k返回绕行。
4. 当堆为空时，一些函数的错误处理很差，例如extract_max。在函数返回值是一种理想的使用模式(与引用参数返回相反)的情况下，尽管错误的用法无法返回任何合理的值，但我发现最简单的方法是允许用户注册回调以便在严重错误时调用，然后返回最不可能导致用户代码中难以查找的错误的内容。在返回一个整数时，这通常归结为返回零。这样的回调通常会终止程序，但用户也可以优雅地恢复。
5. 不确定您的需求，但是display函数打印到cout在很少的情况下是有用的。我喜欢更灵活的版本，用户为每个元素提供自己的“显示”函数: void (void(Int)){ for(auto : v) f(x)；}

我觉得代码是可读的。做得好。