Priority Queue Heap: fixing bubbleDown method

Question

I'm working on a priority queue (heap) and think I have a good ground basis. I think my methods all make sense for the most part but really struggling on my bubbleDown and deleteMin methods.

public class Heap {
    private int n;
    private Node[] s;

    public Heap() {
        s =  new Node[128];
        n =0;
    }

    public boolean isEmptySet() {
        return (n == 0);
    }   

    public Node findMin() {
        return s[0];
    }

    public void insert(Node p) {
        s[n] = p;
        n = n+1;
        bubbleUp(n - 1); // needs to subtract 1 because we do the addition
        }

    public void bubbleUp(int index) {
        if (index == 0) {
            return index;
        }

        else if (index > 0) {
            int parentIndex = (index - 1) / 2; // Might not need to subtract 1
            if (s[index].getKey() < s[parentIndex].getKey()) {
                swapNode(index, parentIndex);
                bubbleUp(parentIndex);
            }
        }
    }

    public void swapNode(int index, int parentIndex) {
        Node temp = s[index];
        s[index] = s[parentIndex];
        s[parentIndex] = temp;
    }

    public void deleteMin(Node p) {
        n = n - 1;
        bubbleDown(s[0], s[n]);
        return s[n];
    }


    public void bubbleDown(int index) {
        if (index < 0) {
            int leftChildIndex = (i*2) + 1;
            int rightChildIndex = (i*2) + 2;
            if (s[index].getKey() > s[leftChildIndex].getKey()) {
                swapNode(index, leftChildIndex);
                bubbleDown(leftChildIndex);
            } else if (s[index].getKey() < s[leftChildIndex].getKey() && s[index].getKey() > s[rightChildIndex].getKey()) {
                swapNode(index, rightChildIndex);
                bubbleDown(rightChildIndex);
            }
        }
    }
}

Answer 1

First, in your bubbleUp(), you do need to subtract 1 to find the parent. Consider that the children of 0 are 1 and 2. If you didn't subtract 1 before dividing, then the parent of 2 would be incorrectly be computed as 1.

In your findMin(), you should check for an empty heap before blindly returning the root item. I know that you have an isEmptySet() function, but findMin() should throw an exception if you call it for an empty heap.

Now, on your deleteMin() and bubbleDown(). deleteMin should be:

public void deleteMin(Node p){
    n = n - 1;
    // place root node at the end of the heap,
    // and the last node at the root.
    swapNode(0, n);

    // adjust the heap
    bubbleDown(0);
    return s[n];
}

The way you had it, deleteMin was passing nodes rather than node indexes to bubbleDown, and it was passing two parameters when bubbleDown only accepts one.

Your bubbleDown is on the right track, but you have to be careful. The rule for bubbling down is that if the node is larger than either of its children, you swap the node with the smallest of the two children. And you can't blindly check both potential children, because the node might not have children at all. So:

public void bubbleDown(int index){
    int childIndex = (index * 2) + 1;
    if (childIndex > n)
    {
        // if the first child index is off the end of the heap
        // then the item has no children. (It's a leaf.)
        return;
    }

    // first find the smallest child
    // This test is to prevent checking a right child that doesn't exist.
    if (childIndex < n)
    {
        if (s[childIndex] > s[childIndex+1])
        {
            childIndex = childIndex + 1;
        }
    }

    // childIndex holds the index of the smallest of the node's children.
    // swap if the parent is larger than the smallest child,
    // and then keep bubbling down.
    if (s[index] > s[childIndex])
    {
        swapNode(index, childIndex);
        bubbleDown(childIndex);
    }
}