r/javahelp • • Oct 26 '20

Solved Trying to implement a MinHeap.*help needed*

Hello, so I'm trying to create a Min-heap with the bottom up approach that takes O(n) time and have spent hours debugging it (~6-7 hrs) but still can't figure out what's wrong with it. The heapify() isn't working as it should, if anyone were to point out the problem it'd be a tremendous help. I'm assuming the problem is in the SiftDown() func, what can't exactly figure out what it could be. I'm linking the code below.

Min-Heap Source Code

Apart from the heapify method, any other corrections/optimizations are also welcome.

private void heapify() {
        int i = size / 2;
        while (i >= 0) {
            siftDown(i--);
        }
    }
private void siftDown(int i) {
        while (minChild(i) != -1) {
            if (heap[i] > heap[minChild(i)]) {
                swap(i, minChild(i));
            }
            i = minChild(i);
        }
    }
private int minChild(int x) {
        if (left(x) >= size) {
            return -1;
        }
        if (right(x) >= size) {
            return left(x);
        }
        return heap[left(x)] < heap[right(x)] ? left(x) : right(x);
    }
private void swap(int i, int j) {
        int t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }

I realised I haven't provided an example test-case where this is going wrong so here you go:

INPUT:

[5, 4, 3, 2, 1]

OUTPUT:

[1, 5, 3, 2, 4]

As you can see output is not a heap.

UPDATED

private void siftDown(int i) {
        while (minChild(i) != -1) {
            int child = minChild(i);
            if (heap[i] > heap[child]) swap(i, child);
            else break; // edit3*
            i = child;
        }
    }

Edit1: Already posted this on r/learnprogramming but no one replied.

Edit2: So I put the required amount of code I need the help with, if that helps. Please understand that it is also frustrating for me to debug this, if you can't figure out the bug please consider upvoting this so that someone else can and don't ghost this post. I really want to move forward with heaps now to fib heaps. Thank you.

Edit3: (final) So as u/heckler82 suggested, the minChild returned different indices after the swap so I stored the original result in a temp variable and updated i with the temp variable's value instead of calling minChild again. Thanks Everyone for helping, anyways I'm posting the updated siftDown function here incase this helps anyone in the future.

Edit3*: Optimization by u/sweetno Break off the loop if heap property is satisfied.

17 Upvotes

12 comments sorted by

•

u/AutoModerator Oct 26 '20

Please ensure that:

  • Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions

  • You include any and all error messages in full

  • You ask clear questions

  • You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

    Trying to solve problems on your own is a very important skill. Also, see Learn to help yourself in the sidebar

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block (old reddit: empty line before the code, each code line indented by 4 spaces, new reddit: https://imgur.com/a/fgoFFis) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost. Just use the edit function of reddit to make sure your post complies with the above

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

4

u/heckler82 Intermediate Brewer Oct 26 '20 edited Oct 26 '20

I think your problem is when you set i = minChild(i);. After swapping the 1 and the 5 i is still equal to 0, but you've changed the state of the array. When you get the minChild for index 0 again in the assignment, you are now comparing 5 and 3 (instead of 1 and 3), so the algorithm returns the index for 3 (which has no children), and the algorithm terminates after that.

1

u/DistinctRain9 Oct 26 '20 edited Oct 26 '20

What would you suggest I change? Because siftDown is supposed to continue as long as the parent element is more than one of the child elements (for minheaps).

Edit: never mind figured it out. Thanks man.

1

u/heckler82 Intermediate Brewer Oct 26 '20

What I would do is save the index of the minimum child at the start of the while loop and replace every call to minChild(i) with that value

while(minChild(i) != -1) { // This minChild should stay
    int min = minChild(i);
    if (heap[i] > heap[min]) { ...

If you do that, and replace all the other minChild calls in your method with min that should work. Maybe. I'm at work, so I can't take an extended look at it. However, saving the index and using that instead of continually calling minChild allows you to work with the same index regardless of whether the array changes or not

1

u/DistinctRain9 Oct 26 '20

Ya it did, It actually popped into my head while asking what should I do, so I updated my post. Thanks for taking out time for this while you're at work.

2

u/sweetno Oct 26 '20

Braces in siftDown are missing for if?

4

u/DistinctRain9 Oct 26 '20

Nope, no identation errors, it's a logical error somewhere. And I don't use braces for single line ifs, makes the code cluttered.

3

u/firsthour Profressional developer since 2006 Oct 26 '20

I would encourage you to please start doing that.

1

u/DistinctRain9 Oct 26 '20 edited Oct 26 '20

I'll keep that in mind for my future codes and I've made the changes here. Now only if my code were to start working...

well look at that, it did!

1

u/sweetno Oct 26 '20

Actually I don’t care about braces around single statements too. I meant that maybe “i = minChild(i)” should’ve been inside of the if, since when heap[i] <= heap[minChild(i)] you’re effectively done with the loop. The heap condition will be already satisfied on the lower levels of your “heap collection” that you’re merging.

1

u/DistinctRain9 Oct 26 '20

Ah got what you meant to say, actually I modified my code with an 'else break' to do what you just said and it would break off the loop before doing unnecessary iterations. But actually that wasn't the bug, it was what op pointed out (I've written in edit3) the indices were getting modified after swap was called and I was updating i's value to the modified index instead of the original one. Thanks anyways I misunderstood what you meant to say in the beginning, am updating the description.

1

u/AutoModerator Oct 26 '20

Please ensure that:

  • Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions

  • You include any and all error messages in full

  • You ask clear questions

  • You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

    Trying to solve problems on your own is a very important skill. Also, see Learn to help yourself in the sidebar

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost. Just use the edit function of reddit to make sure your post complies with the above

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.