Min Binary Heap issue

Question

i need help with this minheap code:

#include < vector>

using namespace std;

class heap {

    vector <int> v;

    public:

        int hSize()
        {
            return v.size();
        }

        int rsize()
        {
            return  hSize() - 1;
        }    

        int parent(int i) 
        {
            return (i - 1) / 2;
        }

        int left(int i)
        {
            return i * 2 + 1;
        }

        int right(int i)
        {
            return i * 2 + 2;
        }

        void swap(int i, int j)
        {
            int temp = v[j];
            v[j] = v[i];
            v[i] = temp;
        }

        void push(int e)
        {

            v.push_back(e);
            int id = rsize(); 

            if (hSize() > 1)
                while (v[parent(id)] > v[id]) {               
                    swap(parent(id), id);
                    id = parent(id);
                }
        }

        int pop ()
        {

          int f = 0;  
          int p = v[0];

          v[0] = v[rsize()];

          if (hSize() > 1) {
              while (v[left(f)] < v[f] || v[right(f)] < v[f]) {
                    if (v[left(f)] < v[f] && v[right(f)] < v[f]) {
                        if (v[left(f)] < v[right(f)]) {
                            swap(left(f), f);
                            f = left(f);
                    }
                    else { 
                            swap(right(f), f);
                            f = right(f);
                    }
                }

                else {
                    if (v[left(f)] < v[f]){
                         swap(left(f), f);
                         f = left(f);
                    }
                    else {
                         swap(right(f), f);
                         f = right(f);
                        }
                    }
                } 
          }
          else { }

          v.resize(rsize());
          return p;
        }

        void show()
        {
            if (hSize() > 0) {
                cout << "Heap content: ";
                for (int i = 0; i < hSize(); i++) cout << v[i] << " ";
            }
            else cout << "\nHeap successfully emptied!";  
            cout << "\n";          
        }

        bool Empty()
        {
            return v.empty();
        }

        ~heap()
        {
            v.clear();
        }

    };         

Well, the code does almost everything right, except when it pops the last element on the screen it prints a random number. What's your opinion?

Thanks!

Answer 1

Debugging

• You can run the code with valgrind to see if it reports any errors.
• You can run the code within a debugger (takes longer to debug but more likelihood of success).

Coding You should use assertions. For example, the first line of the swap function can be assert(i >= 0 && i < v.size()); and similarly for j. I suspect putting these two assertions in will tell you the errors. When you're done, if you like you can comment out the assertions (although some people like to leave some of the assertions on always).

Update Your code was alright. Just needed to add the bounds check inside swap and return if not satisfied. Here is the code and the test case (which passed when I ran):

#include <vector>
#include <iostream>
#include <cassert>
#include <cstdlib>

using namespace std;

class heap {

    vector <int> v;

    public:

        int hSize()
        {
            return v.size();
        }

        int rsize()
        {
            return  hSize() - 1;
        }

        int parent(int i)
        {
            return (i - 1) / 2;
        }

        int left(int i)
        {
            return i * 2 + 1;
        }

        int right(int i)
        {
            return i * 2 + 2;
        }

        void swap(int i, int j)
        {
            //assert(i >= 0 && i < v.size()); 
            //assert(j >= 0 && j < v.size()); 
            if(i >= v.size() || j >= v.size()) return;
            int temp = v[j];
           v[j] = v[i];
            v[i] = temp;
        }

        void push(int e)
        {

            v.push_back(e);
            int id = rsize();

            if (hSize() > 1)
                while (v[parent(id)] > v[id]) {
                    swap(parent(id), id);
                    id = parent(id);
                }
        }

        int pop ()
        {

          int f = 0;
          int p = v[0];

          v[0] = v[rsize()];

          if (hSize() > 1) {
                  while (v[left(f)] < v[f] || v[right(f)] < v[f]) {
                          if (v[left(f)] < v[f] && v[right(f)] < v[f]) {
                                  if (v[left(f)] < v[right(f)]) {
                                          swap(left(f), f);
                                          f = left(f);
                                  }
                                  else {
                                          swap(right(f), f);
                                          f = right(f);
                                  }
                          }

                          else {
                                  if (v[left(f)] < v[f]){
                                          swap(left(f), f);
                                          f = left(f);
                                  }
                                  else {                                         swap(right(f), f);
                                          f = right(f);
                                  }
                          }
                  }
          }
          else { }

          v.resize(rsize());
          return p;
        }

        void show()
        {
                if (hSize() > 0) {
                        cout << "Heap content: ";
                        for (int i = 0; i < hSize(); i++) cout << v[i] << " ";
                }
                else cout << "\nHeap successfully emptied!";
                cout << "\n";
        }

        bool Empty()
        {
                return v.empty();
        }

        ~heap()
        {
                v.clear();
        }

};


int main()
{
        heap h;
        for(int i = 0; i < 10; i++) {
        h.push(rand()%10);
        h.push(4);
        h.push(3);
        h.push(2);
        h.push(1);
        h.push(0);
        h.push(5);
        h.push(-6);
        h.push(7);
        h.show();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.pop();
        h.show();
        }
}

After putting the assertion in, I ran the code in the debugger to find that the crash occurred in the line swap(right(f), f); and right(f) was out of bounds.

Answer 2

You have two similar problems, one in push() and one in pop(). In push you need to check that id != 0 before looking at v[parent(id)]. If id == 0you are at the root and you should halt. Similarly, in pop() you should check if right(f) (or left(f)) is within the vector before accessing v[right(f)] (or v[left(f)]). If it is not, you have reached the bottom of the heap and you should halt.