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.