ansaurus

Question

Min Binary Heap issue

Answer 1

+1 A:

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.

Amit Kumar 2010-02-25 09:28:55

well after putting those two it says "Assertion failed" and the program crashes, any idea why?

2010-02-25 09:44:30

@vladdx I tried running the code but it works for me (no crash). Can you please add a test case or main() function in your question so I can reproduce the crash?

Amit Kumar 2010-02-26 02:54:46

@vladdx You can otherwise try running the code (with the assertion in place) inside gdb debugger (if you are using linux; but for running on gdb you need to compile the code with "g++ -g3"). At the place it crashes, you can view the stack with "bt" command. You can traverse the stack with "up" and "down" commands, and print the value of a variable using "p <variable name>" command. So you can see if the value of `i` and `j` make sense.

Amit Kumar 2010-02-26 02:56:42

@vladdx Please see my updated answer.

Amit Kumar 2010-02-26 03:32:35

Yes, it works now Amit, thanks a lot!Now to code the pathfinding algorithm! :)

2010-02-26 04:16:50

Answer 2

+1 A:

It seems the assertion fails, anyone any new ideas?

2010-02-25 10:09:58

Answer 3

+2 A:

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.

Ari 2010-02-25 12:29:16

Well after doing what you said for i.e. 13, 5, 1, 3 ,17 prints 1, 3, -xxxxxxx, 5, 13 so another problem.What do you think?

2010-02-26 03:55:51

Answer 4

A:

Hi I also need an implementation for decreaseKey(). Are you able to help me? Sammy [email protected]

2010-08-11 21:18:11

ansaurus

tags:

views:

answers:

Min Binary Heap issue

related questions