Implementation of a binary heap

Question

I've read a little about binary heaps/priority queues and decided to try my hand at making my own implementation of one. I'm not the most experienced programmer and I would be really grateful if you guys could take a look at my heap class and tell me if it's a good implementation.

What can I improve here? Any feedback is welcome.

public class Heap<T extends Comparable<? super T>> {

    private T[] array = (T[])new Comparable[10];
    private int size = 0;

    public void insert(T data) {
        if(size+1 > array.length) expandArray();

        array[size++] = data;
        int pos = size-1;
        T temp;

        while(pos != 0 && array[pos].compareTo(array[pos/2]) < 0) {
            temp = array[pos/2];
            array[pos/2] = array[pos];
            array[pos] = temp;
            pos /= 2;
        }
    }

    public T deleteMin() {
        T min = array[0];

        array[0] = array[size-1];
        array[size-1] = null;
        size--;
        int pos = 0;
        T temp;
        boolean done = false;

        while(pos*2+1 < size && !done) {
            int minChild = pos*2+1;
            if(array[minChild].compareTo(array[pos*2+2]) > 0) minChild = pos*2+2;

            if(array[pos].compareTo(array[minChild]) > 0) {
                temp = array[minChild];
                array[minChild] = array[pos];
                array[pos] = temp;
                pos = minChild;
            }
            else done = true;
        }

        return min;
    }

    private void expandArray() {
        T[] newArray = (T[])new Comparable[array.length*2];

        for(int i = 0; i < array.length; i++)
            newArray[i] = array[i];

        array = newArray;
    }
}

Answer 1

1. The API of your class: in my opinion, there should be one more method: getMin that returns the minimum element but not removes it. The only way to get it now without deleting is to call deleteMin and then re-insert it into the heap, which is inconvenient and inefficient.

2. There is a bug in the deleteMin method. The fact that pos * 2 + 1 is less than size does not imply that pos * 2 + 2. It can lead to a NullPointerException. I have written a simple unit test that exposes the problem:

   import org.junit.Test;
   
   import static org.junit.Assert.*;
   
   public class HeapTest {
   
       @Test
       public void testDelete() throws Exception {
           Heap<String> aHeap = new Heap<String>();
           aHeap.insert("a");
           aHeap.insert("b");
           aHeap.insert("c");
           assertEquals("a", aHeap.deleteMin());
       }
   }
   

   The result:

   java.lang.NullPointerException
       at java.lang.String.compareTo(String.java:1142)
       at java.lang.String.compareTo(String.java:111)
       at Heap.deleteMin(Heap.java:33)
       at HeapTest.testDelete(HeapTest.java:13)
   

   You should always test your code in a systematic manner. Unit tests are a good way to do it. They will help you to find and fix bugs and to make sure that it works properly(but not to prove its correctness, of course). They will increase maintainability and reliability of your code. You should write unit tests for all public methods. Do not forget to test edge cases(deleting an element from an empty heap and so on).

3. You expand an array when necessary, but you never shrink it. It can lead to a big memory overhead. For example, if we insert a lot elements into the heap and then remove most of them, the array will not shrink, consuming much more memory than necessary. You can fix it by either adding a shrinkArray method or by using a List instead of an array here. An ArrayList can handle all required operations for you. So I would use it, unless you decided not to use a List on purpose as an exercise. If it is the case, I'd still recommend creating another class that implements the List interface(or provides a similar functionality) to decouple a heap from a dynamic array. It will make your code more readable, flexible(what if you decide to change the implementation of a dynamic array one day?) and testable.

4. Code style:

   • It is conventional to surround binary operators with whitespaces. There should also a whitespace between an if, for or while keyword and an opening parenthesis. Here is a small piece of your code rewritten according to the style conventions:

     while (pos != 0 && array[pos].compareTo(array[pos / 2]) < 0) {
         temp = array[pos / 2];
         array[pos / 2] = array[pos];
         array[pos] = temp;
         pos /= 2;
     }
     

   • Blank lines: a lot of blank lines inside one method don't look good, in my opinion. They can be used for separating different logical blocks of code from each other(but in this case it might be better to create two separate methods instead), but they are definitely redundant in small methods(which is the case here).

   • In general, it is possible to make your code more concise by using the Java standard library. For instance, you can use an Arrays.copyOf method instead of the expandArray. But I believe that it is fine here because it is an exercise, not a production code(otherwise, you could have just used a PriorityQueue, but that's obviously not what you want in this case).

5. You should write doc comments for all public classes and methods.

Summary:

To improve you code, you can do the following:

1. Write unit-tests.

2. Write doc comments.

3. Adhere to the code style conventions.

4. Design classes in such a way that one class is responsible for one concern.

Answer 2

Another bug

In addition to the bug found by @kraskevitch, this is a bug too:

while(pos != 0 && array[pos].compareTo(array[pos/2]) < 0) {
    temp = array[pos/2];
    array[pos/2] = array[pos];
    array[pos] = temp;
    pos /= 2;
}

It seems you assume that pos / 2 is the index of the parent, but it's not. The index of the parent would be (pos - 1) / 2.

Simplify using helper methods

Typing out (pos - 1) / 2 to get the parent's position is not very practical. It's better to store it in a variable:

int parentPos = (pos - 1) / 2;
while (pos != 0 && array[pos].compareTo(array[parentPos]) < 0) {
    temp = array[parentPos];
    array[parentPos] = array[pos];
    array[pos] = temp;
    pos = parentPos;
    parentPos = (pos - 1) / 2;
}

In fact, it would be best to put this index calculation into a helper method rather then repeatedly typing out every time:

private int getParentIndex(int index) {
    return (index - 1) / 2;
}

I suggest to do the same for calculating the left and right child positions, and to cache the values in a variable when you reuse the same values many times.

Single responsibility principle

The logic for expanding the storage is split in two places:

• The insert method checks if it's necessary to expand storage
• The expandArray method expands the storage

Rather than splitting this logic in two methods and making insert share this responsibility with expandArray, it would be better to "rephrase" the expandArray method as ensureCapacity:

private void ensureCapacity(int targetSize) {
    if (array.length < targetSize) {
        array = Arrays.copyOf(array, array.length * 2);
    }
}

And then insert can simply do this:

public void insert(T data) {
    ensureCapacity(size + 1);
    // ...

Be suspicious about flag variables

The done variable in the deleteMin method looks fishy. It's part of the loop condition, and it's set at the end of the loop. Is it possible to replace it with a simple break? Yes it is!