Binary Heap Implementation in Java

Question

Here's my array-based binary heap java implementation, looking for comments / suggestions on my approach. I used a base heap class to contain most of the logic, since the behavior of min/max heaps is quite similar. I found the array-based implementation quite simple to build compared to a tree-based structure, only mechanic I can really think to add at this point is a dynamically-resizing underlying array, instead of using a fixed-size only.

Base Heap abstract class:

public abstract class Heap<T extends Comparable<T>> {

    protected T[] heap;
    protected final int maxSize;
    protected int size;

    public Heap(Class<T> clazz, int maxSize) {
        this.maxSize = maxSize;
        this.heap = (T[]) Array.newInstance(clazz, this.maxSize);
        this.size = 0;
    }

    /**
    * Inserts an element into the heap.
    * @param data item to insert.
    * @throws HeapException
    */
    public void insert(T data) throws HeapException {
        if(this.size >= this.maxSize) {
            throw new HeapException();
        }
        this.heap[this.size] = data;
        upHeap();
        this.size++;
    }

    /**
    * Returns the current extreme value within the heap.
    * @return object representing current extreme value.
    * @throws HeapException
    */
    public T getExtreme() throws HeapException {
        if(isEmpty()) {
            throw new HeapException();
        }
        return this.heap[0];
    }

    /**
    * Returns and removes the current extreme value from within the heap, replacing the old extreme with the next candidate.
    * @return object representing extreme value.
    * @throws HeapException
    */
    public T removeExtreme() throws HeapException {
        if(isEmpty()) {
            throw new HeapException();
        }
        T extreme = this.heap[0];
        this.heap[0] = this.heap[this.size - 1];
        this.heap[this.size - 1] = null;
        this.size--;
        downHeap();
        return extreme;
    }

    /**
    * 'Bubbles-up' an item from the bottom of the heap (tail of the array) into it's appropriate spot, following the rules of a Min Heap.
    */
    protected void upHeap() {
        int currentIndex = this.size;
        while(currentIndex > 0) {
            int parentIndex = (currentIndex % 2 == 0) ? (currentIndex / 2) - 1 : currentIndex / 2;
            if(upHeapComparator(currentIndex, parentIndex)) {
                break;
            }
            swap(currentIndex, parentIndex);
            currentIndex = parentIndex;
        }
    }

    /**
    * Percolates-down an item from the top of the heap (head of the array) into it's appropriate spot, following the rules of the underlying heap class.
    */
    protected void downHeap() {
        int currentIndex = 0;
        while(true) {
            int leftChildIndex = (2 * currentIndex) + 1;
            int rightChildIndex = (2 * currentIndex) + 2;
            if(leftChildIndex < this.size && rightChildIndex < this.size) {
                int extremeIndex = findExtremeIndex(leftChildIndex, rightChildIndex);
                if(downHeapComparator(currentIndex, extremeIndex)){
                    swap(currentIndex, extremeIndex);
                    currentIndex = extremeIndex;
                } else {
                    break;
                }
            }
            else if(leftChildIndex < this.size) {
                if(downHeapComparator(currentIndex, leftChildIndex)) {
                    swap(currentIndex, leftChildIndex);
                    currentIndex = leftChildIndex;
                } else {
                    break;
                }
            }
            else {
                break;
            }
        }
    }

    /**
    * Comparison method used with up-heap operations, to be overridden within inheriting class.
    * @param xIndex first index to use within comparison.
    * @param yIndex second index to use within comparison.
    * @return true or false based on the inheriting class' implementation.
    */
    protected abstract boolean upHeapComparator(int xIndex, int yIndex);

    /**
    * Comparison method used with down-heap operations, to be overridden within inheriting class.
    * @param xIndex first index to use within comparison.
    * @param yIndex second index to use within comparison.
    * @return true or false based on the inheriting class' implementation.
    */
    protected abstract boolean downHeapComparator(int xIndex, int yIndex);

    /**
    * Comparison method used when finding an extreme value, to be overridden within inheriting class.
    * @param xIndex first index to use within comparison.
    * @param yIndex second index to use within comparison.
    * @return true or false based on the inheriting class' implementation.
    */
    protected abstract boolean extremeComparator(int xIndex, int yIndex);

    /**
    * Compares two values within the underlying heap array and returns the index of the maximum.
    * @param xIndex index of first item to use in comparison.
    * @param yIndex index of second item to use in comparison.
    * @return integer representing index of the maximum value from the comparison.
    * @throws IndexOutOfBoundsException
    */
    protected int findExtremeIndex(int xIndex, int yIndex) throws IndexOutOfBoundsException {
        if(xIndex >= this.size || yIndex >= this.size) {
            throw new IndexOutOfBoundsException();
        }
        return (extremeComparator(xIndex, yIndex)) ? xIndex : yIndex;
    }

    /**
    * Quick method used to swap two items within the underlying heap array.
    * @param xIndex index of first item to swap.
    * @param yIndex index of second item to swap.
    * @throws IndexOutOfBoundsException
    */
    protected void swap(int xIndex, int yIndex) throws IndexOutOfBoundsException {
        if(xIndex > this.size || yIndex > this.size) {
            throw new IndexOutOfBoundsException();
        }
        T temp = this.heap[xIndex];
        this.heap[xIndex] = this.heap[yIndex];
        this.heap[yIndex] = temp;
    }

    /**
    * Compares two values.
    * @param x first value to use in comparison.
    * @param y second value to use in comparison.
    * @return
    */
    protected int compare(T x, T y) {
        return x.compareTo(y);
    }

    /**
    * Returns the heap in array form.
    * @return array of generic objects representing the heap.
    */
    public T[] getHeap() {
        return this.heap;
    }

    /**
    * Returns the allotted maximum size of the underlying heap array.
    * @return an integer representing maximum size of the heap.
    */
    public int getMaxSize() {
        return this.maxSize;
    }

    /**
    * Returns the current number of elements present within the underlying heap array.
    * @return an integer representing the current number of elements within the heap.
    */
    public int getSize() {
        return this.size;
    }

    /**
    * Determines whether or not the heap contains any elements.
    * @return true if the heap is empty, false if otherwise.
    */
    public boolean isEmpty() {
        return this.size <= 0;
    }

}

Min-Heap implementation, extending base Heap class:

public class MinHeap<T extends Comparable<T>> extends Heap<T> {

    public MinHeap(Class<T> clazz, int maxSize) {
        super(clazz, maxSize);
    }

    @Override
    protected boolean upHeapComparator(int xIndex, int yIndex) {
        return this.heap[xIndex].compareTo(this.heap[yIndex]) >= 0;
    }

    @Override
    protected boolean downHeapComparator(int xIndex, int yIndex) {
        return compare(this.heap[xIndex], this.heap[yIndex]) > 0;
    }

    @Override
    protected boolean extremeComparator(int xIndex, int yIndex) {
        return this.heap[xIndex].compareTo(this.heap[yIndex]) <= 0;
    }

}

Max-Heap implementation, extending base Heap class:

public class MaxHeap<T extends Comparable<T>> extends Heap<T> {

    public MaxHeap(Class<T> clazz, int maxSize) {
        super(clazz, maxSize);
    }

    @Override
    protected boolean upHeapComparator(int xIndex, int yIndex) {
        return this.heap[xIndex].compareTo(this.heap[yIndex]) < 0;
    }

    @Override
    protected boolean downHeapComparator(int xIndex, int yIndex) {
        return compare(this.heap[xIndex], this.heap[yIndex]) <= 0;
    }

    @Override
    protected boolean extremeComparator(int xIndex, int yIndex) {
        return this.heap[xIndex].compareTo(this.heap[yIndex]) > 0;
    }

}

Supplementary HeapException class:

public class HeapException extends Exception {

    public HeapException() {
        super();
    }

    public HeapException(String message) {
        super(message);
    }
}

Answer 1

        while(true) {
            int leftChildIndex = (2 * currentIndex) + 1;
            int rightChildIndex = (2 * currentIndex) + 2;
            if(leftChildIndex < this.size && rightChildIndex < this.size) {
                int extremeIndex = findExtremeIndex(leftChildIndex, rightChildIndex);
                if(downHeapComparator(currentIndex, extremeIndex)){
                    swap(currentIndex, extremeIndex);
                    currentIndex = extremeIndex;
                } else {
                    break;
                }
            }
            else if(leftChildIndex < this.size) {
                if(downHeapComparator(currentIndex, leftChildIndex)) {
                    swap(currentIndex, leftChildIndex);
                    currentIndex = leftChildIndex;
                } else {
                    break;
                }
            }
            else {
                break;
            }
        }

You could get rid of the duplicate code with something like

        for (int left = (2 * currentIndex) + 1; left < size; left = (2 * currentIndex) + 1) {
            int right = left + 1;
            int extreme = right < size ? findExtremeIndex(left, right) : left;

            if (!downHeapComparator(currentIndex, extreme)) {
                return;
            }

            swap(currentIndex, extreme);
            currentIndex = extreme;
        }

I changed the names to be shorter to eliminate scrolling in the code block. While I would find these names sufficient, you can of course use the longer ones instead. Outside the specific issues of displaying code here, there's no reason not to use the longer names.

This moves the question of whether there is a right child into the selection of extreme. Otherwise, the handling of swapping can be the same in both branches.

In Java, you only need to use this. to disambiguate. You can use it to indicate which variables are object fields, but you do not have to do so. It's your choice. I choose not to use it when I don't need to do so.

I prefer to put a space between control structure keywords like while, for, or if and the parenthesis after them. This helps separate them from method calls like swap.

I have gotten in the habit of breaking or returning on the negative condition. Then I don't have to use extra indent on the positive condition.

I'm not sure that your upHeapComparator and downHeapComparator should be logical opposites. In particular, I think that you should only swap when not equal. When equal, it should be a no-op.

Answer 2

This is good code, but I will still add a couple of pointers. Some of them may be subjective, but if it adds any value, its probably worth it.

1. I felt, the two formats this.heap[xIndex].compareTo(this.heap[yIndex]) < 0; and compare(this.heap[xIndex], this.heap[yIndex]) <= 0; confusing. I understand the whole concept of DRY and stuff, but take it with punch of salt. Make it use the same format.

2. As correctly pointed out by @mdfs13, while(true) can and should be replaced.

3. Professionally, a heap could be extensible, not restricted to fixed size.

4. Each time you throw HeapException, you pass it empty, ie without any string message.

5. Your child classes have upHeapComparator(int xIndex, int yIndex), this can be dangerous since xIndex is supposed to be child and yindex needs to be parent.

6. Your getHeap should return immutable array.

7. Given your implementation you should not encounter if(xIndex >= this.size || yIndex >= this.size) { this condition in findExtremeIndex. Good to have a check, but you could avoid such checks in private methods, since they are in your control.

8. In isEmpty this check this.size == 0 should be enof. No need to check this.size <= 0;

9. You can declare this final too. protected final T[] heap;