3
\$\begingroup\$
     /*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.

\$\endgroup\$
8
  • \$\begingroup\$ The first step should be to fix the warnings and errors when you compile this code. \$\endgroup\$ Jan 21, 2018 at 12:47
  • \$\begingroup\$ I have compiled using c++14. That doesn't give any errors. \$\endgroup\$ Jan 21, 2018 at 13:15
  • 1
    \$\begingroup\$ @RupankPahuja, use -Wall -Wpedantic -Werror. The latter might be overkill in some limited cases, but the first two are usually always used. \$\endgroup\$ Jan 21, 2018 at 13:44
  • 1
    \$\begingroup\$ @RupankPahuja: Maybe no errors. But if you turn on warnings -Wall -Wextra I see 6 warnings. Two seem critical three will cause errors in the long term and the last one is good advice. Remember the "Warnings" by the C++ compiler are logical errors in your understanding of the code. They may be technically legal syntax but will usually result in bugs or undefined behavior. \$\endgroup\$ Jan 21, 2018 at 19:50
  • 1
    \$\begingroup\$ @Incomputable: I always use -Werror it prevents compilation when you have logical bugs. \$\endgroup\$ Jan 21, 2018 at 19:51

1 Answer 1

1
\$\begingroup\$
  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.

\$\endgroup\$
3
  • \$\begingroup\$ The last two points here sound like a C programmer's advice. (4) For error handling, throw an exception. The calling code can choose to catch it or not. Either way things stay clean, an no resources get lost. (5) Instead of print, overload the stream insertion operator. That way the user can choose which stream to write to. Also, it's idiomatic in C++, people will expect it to be present. \$\endgroup\$ Jan 21, 2018 at 19:40
  • \$\begingroup\$ I have many years more experience of C++ than C, yet I have come to prefer C in most scenarios. Exceptions are the C++ way of doing it, and most would agree they come with a number of issues that really can't be solved. Overloading a stream operator is just a pain, but I guess some are code masochists getting payed by the line. \$\endgroup\$
    – Andreas
    Jan 21, 2018 at 20:32
  • 1
    \$\begingroup\$ @Andreas, I believe the problem he is referring to are lack of templates and iterators. Especially in the last case, it could be templated on the Callable type. Upvoted anyway, since it has some good points. \$\endgroup\$ Jan 22, 2018 at 9:37

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.