A heap class implemetation

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

Please suggest possible good code management techniques which can help me write and maintain better code in the future. I think implementing and maintaining data structures could be a good practice on how to maintain code for beginners like me.

Answer 1

1. use the correct numeric domain for your types, e.g. unsigned instead of int for size since negative size is never valid for any data structure. It also simplifies some of the error handling.

2. using namespace in header is a big no-no. If you want to omit std:: in you code you need to localize it, like putting typedefs inside the class declaration or having a .cpp seperate from .h.

3. is_empty might as well return the ternary expression instead of the detour with a temporary bool k.

4. some functions have poor error handling when the heap is empty, such as extract_max. In cases when function return value is a desirable usage pattern (as opposed to return by reference parameter), despite erroneous usage unable to return any reasonable value, I find it most simple to allow users to register a callback to be called on serious errors, and then return whatever is least probable to cause hard-to-find bugs in user code. On returning an integer this usually boils down to returning zero. Such a callback typically terminates the program, but user is also allowed to recover gracefully.

5. not sure about your requirements, but the display function printing to cout is useful in only very few cases. I prefer more flexible version where users provide their own "display" functions to execute for each element:

   void foreach(void f(int)) { 
       for(auto x: v) 
           f(x); 
   }
   

I find the code readable. Good job.