Generic Min Heap Implementation in Java

Question

There is a Min-Heap implementation in Java. BubbleUp() and BubbleDown() could have been coded using recursion but I prefer without recursion. Would there be a major difference if had used recursion?

package heap;

import interfaces.queue.PriorityQueue;
import java.util.Arrays;
import java.util.stream.Collectors;

public class Heap<T extends Comparable<T>> implements 
PriorityQueue<T>
{
    private T[] elements;
    private int size;
    private int capacity;

    public Heap()
    {
        this(500);
    }

    public Heap(int capacity)
    {
        this.capacity = capacity;
        size = 0;
        elements = (T[]) new Comparable[this.capacity];
    }

    public int size()
    {
        return size;
    }

    public boolean isEmpty()
    {
        return size() == 0;
    }

    @Override
    public void add(T data) throws Exception
    {
        if(size() >= capacity) throw new Exception("Heap is full");
        elements[size++] = data;
        bubbleUp();
    }

    private void bubbleUp()
    {
        int child = size() - 1;
        int parent = (child-1)/2;

        while(parent >= 0 && elements[child].compareTo(elements[parent]) < 0)
        {
            swap(child, parent);
            child = parent;
            parent = (child-1)/2;
        }
    }

    @Override
    public T removeMin() throws Exception
    {
        if(isEmpty()) throw new Exception("Empty heap");
        T root = elements[0];
        swap(size()-1, 0);
        elements[size()-1] = null;
        size--;
        bubbleDown();
        return root;
    }

    private void bubbleDown()
    {
        int parent = 0;
        int leftChild = 2*parent + 1;
        int rightChild = 2*parent + 2;

        int choice = compareAndPick(leftChild, rightChild);

        while(choice != -1)
        {
            swap(choice, parent);
            parent = choice;
            choice = compareAndPick(2*choice+1, 2*choice+2);
        }
    }

    private int compareAndPick(int leftChild, int rightChild)
    {
        if(leftChild >= capacity || elements[leftChild] == null) return -1;
       if((elements[leftChild].compareTo(elements[rightChild]) <= 0)|| (elements[rightChild] == null))
            return leftChild;
        return rightChild;
    }

    private void swap(int child, int parent)
    {
        T t = elements[child];
        elements[child] = elements[parent];
        elements[parent] = t;
    }

    @Override
    public String toString()
    {
         return Arrays.stream(elements)
                 .filter(element -> element != null)
                 .collect(Collectors.toList()).toString();
    }
}

Answer 1

Exception handling

Throwing Exception is not recommended because it's too generic. It doesn't give a clue to the caller as to what went wrong. It's recommended to use specific exceptions.

When implementing a collection abstract data type, it's good to take a look at a similar interface in the standard library, for example Deque:

• How do they handle when an element cannot be added due to capacity restrictions? They throw IllegalArgumentException.
• How do they handle when an element is requested but the collection is empty? They throw NoSuchElementException.

As you see, suitable specific exceptions already exist. Also notice that these exceptions are unchecked. It means that callers of these methods don't have to catch them. And that seems an appropriate decision, since the situations in which these exceptions can be thrown are quite unexpected, and should not happen under normal circumstances.

Redundant capacity variable

The member variable capacity is redundant. The same information already exists in elements.length.

Make members final when possible

Since elements is never reassigned, it would be good to make it final, so that you cannot reassign by mistake.

Overriding toString

Keep in mind that toString is not intended for "pretty-printing".

And for printing the content of the heap, this implementation doesn't look useful to me. With the null values removed, the structure of the heap is not visible, and without the structure, the ordering of the elements is meaningless, which can be misleading.

For printing the content of the heap I would suggest adding a dedicated method, keep the nulls, and print values of the first size elements.

Answer 2

I do not endorse recursion when a clean and simple iterative iterative solution is readily available. You did the right thing.

The only problem I have is with compareAndPick implementation. First, rightChild is not tested against capacity, and may cause an out-of-bounds access. Second, testing elements[rightChild] against null looks too late (how does compareTo(null) behave?). Finally, there is really no need to test both an index against capacity and an object against nullness: index < size guarantees both.

You may consider renaming compareAndPick to selectSmallestChild (and choice to child).

Also, I recommend to leave the children computation to compareAndPick, and have a terser version of bubbleDown loop:

    while ((child = selectSmallestChild(parent)) != -1) {
        swap(child, parent);
        parent = child;
    }