BinaryHeap implemented using an array.

Heap.java

package us.kardol.datastructure;

import java.util.Arrays;

/**
 * Created by Guillermo Kardolus on 2/13/16.
 *
 * Wikipedia:
 *  the heap property: If A is a parent node of B then the key of node A is ordered with respect to the key of
 *  node B with the same ordering applying across the heap.
 *  Heaps are usually implemented in an array (fixed size or dynamic array), and do not require pointers between
 *  elements. After an element is inserted into or deleted from a heap, the heap property may be violated and the heap
 *  must be balanced by internal operations.
 */
public class Heap {
    private int[] heap;
    private int heapSize;

    public Heap(int capacity){
        heap = new int[capacity];
        heapSize = 0;

        // Heap will hold positive values only. Fill with arbitrary value.
        Arrays.fill(heap, -1);
    }

    public int insert(int key){
        int tmp;
        int insertPoint = heapSize;

        if(this.isFull() || key < 0){
            throw new HeapException();
        }

        heap[heapSize] = key; // insert at the end

        // reorder
        for(int i = getHeapSize(); getParent(i) >= 0; i = insertPoint) {
            if (key < heap[getParent(i)]) {
                tmp = heap[getParent(i)];
                heap[getParent(i)] = heap[i];
                heap[i] = tmp;
                insertPoint = getParent(i);
            }else if(key == heap[getParent(i)]){ // dupe!
                throw new HeapException();
            }
            else{
                insertPoint = i;
                break;
            }
        }
        heapSize++;
        return insertPoint;
    }

    public int poll(){
        if(this.isEmpty()){
            throw new HeapException();
        }
        int result = heap[0];
        int key = heap[heapSize - 1];
        int tmp;
        int insertPoint;

        heap[0] = key;
        heap[heapSize - 1] = -1;
        heapSize--;

        // reorder
        for(int i = 0; i < this.getHeapSize() - 1; i = insertPoint){
            if(key > getLeftChild(key)){
                tmp = getLeftChild(key);
                heap[i] = tmp;
                heap[2 * i + 1] = key;
                insertPoint = 2 * i + 1;
            }else if(key > getRightChild(key)){
                tmp = getRightChild(key);
                heap[i] = tmp;
                heap[2 * i + 2] = key;
                insertPoint = 2 * i + 2;
            }else{
                break;
            }
        }

        return result;
    }

    public int peek(){
        if(this.isEmpty()){
            throw new HeapException();
        }
        return heap[0];
    }

    public boolean contains(int key){
        for(int i = 0; i < this.heapSize; i++){
            if(heap[i] == key){
                return true;
            }
        }
        return false;
    }

    public boolean isEmpty(){
        if(this.heapSize == 0){
            return true;
        }
        return false;
    }

    public boolean isFull(){
        if(this.heapSize == heap.length){
            return true;
        }
        return false;
    }

    public int getParent(int key){
        int parent = -1;
        if(key > 0){
            parent = (key - 1) / 2;
        }
        return parent;
    }

    public int getLeftChild(int key){
        for(int i = 0; (2 * i + 1) < this.heapSize; i++){
            if(heap[i] == key){
                return heap[2 * i + 1];
            }
        }
        return -1;
    }

    public int getRightChild(int key){
        for(int i = 0; (2 * i + 2) < this.heapSize; i++){
            if(heap[i] == key){
                return heap[2 * i + 2];
            }
        }
        return -1;
    }

    public int getHeapSize(){
        return this.heapSize;
    }

    public int[] getHeap(){
        return this.heap;
    }
}

class HeapException extends RuntimeException{

}

HeapTest.java

package us.kardol.datastructure;

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

import static org.junit.Assert.*;

/**
 * Created by Guillermo Kardolus on 2/19/16.
 */
public class HeapTest {
    Heap heap;

    @Before
    public void setUp() throws Exception {
        heap = new Heap(10);
    }

    @Test
    public void testIsEmptyBeforeInsert() throws Exception {
        assert(heap.isEmpty() == true);
    }

    @Test
    public void testIsFullBeforeInsert(){
        assert(heap.isFull() == false);
    }

    @Test
    public void getParentZero(){
        assertEquals(heap.getParent(0), -1); // no parent
    }

    @Test
    public void getParentOne(){
        assertEquals(heap.getParent(1), 0); // no parent
    }

    @Test
    public void getParentTwoAndThree(){
        assertEquals(heap.getParent(2), 0);
        assertEquals(heap.getParent(3), 1);
    }

    @Test
    public void getParentFourAndFive(){
        assertEquals(heap.getParent(4), 1);
        assertEquals(heap.getParent(5), 2);
    }

    @Test
    public void getParentSixAndSeven(){
        assertEquals(heap.getParent(6), 2);
        assertEquals(heap.getParent(7), 3);
    }

    @Test(expected = HeapException.class)
    public void testInsertIllegalArgument(){
        heap.insert(-5);
    }

    @Test
    public void testInsertOneNode(){
        assertEquals(heap.insert(5), 0); // inserts at index 0
        assertEquals(heap.getHeapSize(), 1);
        assert(heap.contains(5));
    }

    @Test
    public void testInsertSecondNode(){
        heap.insert(5);
        assertEquals(heap.insert(3), 0); // inserts at index 0 again (3 < 5)
        assertArrayEquals(new int[]{3, 5, -1, -1, -1, -1, -1, -1, -1, -1}, heap.getHeap());
    }

    @Test
    public void testInsertThirdNode(){
        heap.insert(5);
        heap.insert(3);
        assertEquals(heap.insert(11), 2);
        assertArrayEquals(new int[]{3, 5, 11, -1, -1, -1, -1, -1, -1, -1}, heap.getHeap());
    }

    @Test
    public void testInsertForthNode(){
        heap.insert(5);
        heap.insert(3);
        heap.insert(11);
        assertEquals(heap.insert(2), 0);
        assertArrayEquals(new int[]{2, 3, 11, 5, -1, -1, -1, -1, -1, -1}, heap.getHeap());
    }

    @Test
    public void testInsertFifthNode(){
        heap.insert(5);
        heap.insert(3);
        heap.insert(11);
        heap.insert(2);
        assertEquals(heap.insert(1), 0);
        assertArrayEquals(new int[]{1, 2, 11, 5, 3, -1, -1, -1, -1, -1}, heap.getHeap());
    }

    @Test
    public void testFullHeap(){
        heap.insert(5);
        heap.insert(3);
        heap.insert(11);
        heap.insert(2);
        heap.insert(54);
        heap.insert(32);
        heap.insert(112);
        heap.insert(21);
        heap.insert(8);
        heap.insert(17);
        assert(heap.isFull());
    }

    @Test(expected = HeapException.class)
    public void testAddTooMany(){
        heap.insert(5);
        heap.insert(3);
        heap.insert(11);
        heap.insert(2);
        heap.insert(54);
        heap.insert(32);
        heap.insert(112);
        heap.insert(21);
        heap.insert(8);
        heap.insert(17);
        heap.insert(18);
    }

    @Test(expected = HeapException.class)
    public void testAddDuplicate(){
        heap.insert(5);
        heap.insert(3);
        heap.insert(3);
    }

    @Test
    public void testPeek(){
        heap.insert(5);
        heap.insert(99);
        heap.insert(3);
        assertEquals(heap.peek(), 3);
    }

    @Test(expected = HeapException.class)
    public void testPeekEmptyHeap(){
        heap.peek();
    }

    @Test(expected = HeapException.class)
    public void testPollEmptyHeap(){
        heap.poll();
    }

    @Test
    public void testGetLeftChild(){
        heap.insert(42);
        heap.insert(12);
        heap.insert(900);
        heap.insert(700);
        heap.insert(9);
        assertEquals(heap.getLeftChild(12), 700);
        assertEquals(heap.getLeftChild(9), 12);

    }

    @Test
    public void testGetRightChild(){
        heap.insert(42);
        heap.insert(12);
        heap.insert(900);
        heap.insert(700);
        heap.insert(9);
        assertEquals(heap.getRightChild(9), 900);
        assertEquals(heap.getRightChild(12), 42);
    }

    @Test
    public void testPoll(){
        heap.insert(15);
        heap.insert(11);
        heap.insert(88);
        assertEquals(heap.poll(), 11);
        assertEquals(heap.getHeapSize(), 2);
        assertArrayEquals(new int[]{15, 88, -1, -1, -1, -1, -1, -1, -1, -1}, heap.getHeap());
    }
}