Binary Min Heap data structure implementation

Question

After reading about heap I tried to implement the heap. Below is my code along with test. Any feedback with respect to correctness, performance is welcome.

import java.util.Arrays;

public class BinaryHeap2 {
    private int[] heap;
    private int size;
    private int capacity;

    public BinaryHeap2(){
        capacity = 100;
        size = 0;
        heap = new int[capacity];
    }

    public BinaryHeap2(int capacity){
        this.capacity = capacity;
        size = 0;
        heap = new int[this.capacity];
    }

    public void offer(int i){

        if(size>=capacity){
            capacity = capacity*2;
            int[] tmp = new int[capacity];
            System.arraycopy(heap, 0, tmp, 0, heap.length);
            heap = tmp;
        }

        heap[size++] = i;

        heapifyUp(size-1);

    }

    private void heapifyUp(int position){
        int parent = (position-1)/2;
        while(heap[parent]>heap[position]){
            swap(parent,position);
            position = parent;
            parent = (position-1)/2;
        }
    }

    private void swap(int i, int j){
        int t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }

    public int peek(){
        return heap[0];
    }

    public int poll(){
        int min = heap[0];
        heap[0] = heap[size-1];
        size--;
        if(size>1)
            heapifyDown(0);
        return min;
    }

    public int getSize(){
        return size;
    }

    private void heapifyDown(int i) {
        int leftChild = 2*i+1;
        int rightChild = 2*i+2;
        int childToSwap = heap[leftChild]<heap[rightChild]?leftChild:rightChild;        
        while(heap[i]> heap[childToSwap]){
            swap(i,childToSwap);
            i = childToSwap;
            leftChild = 2*i+1;
            rightChild = 2*i+2;
            if(rightChild>=size||leftChild>=size)break;
            childToSwap = heap[leftChild]<heap[rightChild]?leftChild:rightChild;
        }

    }

    public void display(){
        System.out.println(Arrays.toString(heap));
    }


}

Below is the Unit test

import static org.junit.Assert.assertEquals;

import org.junit.Before;
import org.junit.Test;

public class BinaryHeap2Test {

    BinaryHeap2 heap;
    @Before
    public void setUp(){
        heap = new BinaryHeap2(3);
    }

    @Test
    public void test() {
        heap.offer(7);
        heap.offer(6);
        heap.offer(3);
        heap.offer(2);
        heap.offer(1);
        heap.offer(5);
        heap.offer(4);
        heap.offer(3);
        heap.offer(2);  
        heap.display();
        assertEquals(1, heap.peek());
        assertEquals(heap.poll(), 1);
        assertEquals(heap.poll(), 2);
        assertEquals(heap.poll(), 2);
        assertEquals(heap.poll(), 3);
        assertEquals(heap.poll(), 3);
        assertEquals(heap.poll(), 4);
        heap.offer(1);
        heap.display();
        assertEquals(heap.poll(), 1);
        assertEquals(heap.poll(), 5);
        assertEquals(heap.poll(), 6);
        assertEquals(heap.poll(), 7);   
        heap.display();

    }

    @Test
    public void test2(){
        heap.offer(300);
        heap.offer(200);
        heap.offer(100);

        assertEquals(100, heap.poll());
        heap.display();
        assertEquals(200, heap.poll());
        heap.display();
        assertEquals(300, heap.poll());
        heap.display();
        heap.offer(2);
        assertEquals(2, heap.peek());
        heap.offer(100);
        heap.offer(1);
        heap.offer(5);
        assertEquals(1, heap.poll());
        assertEquals(2, heap.poll());
        assertEquals(5, heap.poll());
        assertEquals(100, heap.poll());
    }

}

Answer 1

• You have duplicated code in your constructors, the default constructor should call the other one with capacity.
• Maybe make the capacity = 100 constant and name it something like DEFAULT_INITIAL_CAPACITY.
• Your tests are not named. After reading a name of a test (or anything you name in general) you should have some sort of understanding, what the test tests.
• You test too many things at once. One test should test one aspect of your code. You call offer n times and assert the peek value, after that you poll and offer and assert the poll value. Better would be to split it and test the poll and offer mechanism seperately. So actually the first part could fail, while the second one would be okay, or the other way round. So you are never really sure, what really failed. You also don't have to call offer n times, it shouldn't make any difference, does it? If it would, it should be a separate test anyway.

• test2() isn't meaningful, either, I mean, what's the difference between the first test, except larger numbers? I'm sure you want to test the resize of the inner array, but how does one know? I'd do something like this:

  @Test
  public void exceedingHeapsizeCapacityIncreaseHeapCapacity() {
      int heapCapacity = 1;
      BinaryHeap2 heap = new BinaryHeap2(1);
  
      heap.offer(1);
      heap.offer(1);
  
      // no assertion, if resize wouldn't work, 2nd call would throw Exception... maybe a method to provide the actual capacity wouldn't be _that_ bad
  }
  

• To call 'display' in a test doesn't make sense either, if you have thousands of test in an application, you just fill the console with crap and makes actual troubleshooting much harder, better to have debug or trace debugging within the class under test and activate it, when you have to troubleshoot your test or something in production.

• The type has a "display" method. Usually you have an own 'View' Type. You just pass your Heap and tell the View "display your contents" (think as if you want to change the 'presentation layer', like, if you want to display it in a browser as html, the type must not write html itself)
• Try to avoid naming variables like i and j. If you read the method swap by itself, you do not know, what i and j means, a method shall be as self explanatory as possible. To really understand it, you have to check, who actually calls this method.
• The intention of heapifyDown is not very clear. I've read it three times and still don't understand it - goal should be, that you can read it once and understand it, shouldn't it? I think that's possible in that case. The break in the while loop hurts, can't you do that within the while condition, too?
• The ordering of of public/private methods is always a discussion. It usually is public to private. But I also like to order it as how the code is called. Like you have public void offer, and you call heapifyUp, which is just under it, which I actually really like. But: The getSize() can moved beneath heapifyDown.

Answer 2

• heapifyDown tests for the children existence in the loop, but misses this test at the very beginning. If size == 2, it would try to access a non-existent right child.

• Similarly, the loop may break a bit early:

      if(rightChild>=size||leftChild>=size)break;
  

  breaks if there is no rightChild. However, leftChild may well exist, and require swap.

• Computation of childToSwap looks somewhat crowded. Considering special cases above it is worth to factor it out into a (private) method.

• I would consider shrinking the heap when the ratio of size/capacity goes below a certain threshold.