BinaryHeap.java

/**
 *
 * @author Meluleki Dube
 */
public class BinaryHeap {

    private int heap[];
    private int index;

    public BinaryHeap(int initcap) {
        heap = new int[initcap];
        index = 0;
    }

    /**
     * Swaps to numbers in the indexes given
     *
     * @param index1
     * @param index2
     */
    private void swap(int index1, int index2) {
        heap[index1] = heap[index1] ^ heap[index2];
        heap[index2] = heap[index1] ^ heap[index2]; //so we get whatever was in index 1
        heap[index1] = heap[index1] ^ heap[index2]; //this gives us wat was in index 2
    }

    /**
     * This method inserts a new value to the heap. if the heap is out of space
     * we create new space to accomodate the new item
     *
     * @param value The item we are going to add in to the heap
     */
    public void insert(int value) {
        if (++index == heap.length) {
            _rebuildHeap();
        }
        heap[index] = value;
        heapify();
    }

    /**
     * Method to fix the heap after inserting a new items
     */
    private void heapify() {
        int temp_index = index;
        int parent_index;
        boolean changed = true;
        while (changed && temp_index > 1) {//after root there is no looking futher
            parent_index = temp_index / 2; //get the parrent node
            if (heap[temp_index] < heap[parent_index]) {//we need to swap if this is the case
                swap(temp_index, parent_index);
                temp_index = parent_index;
            } else {
                changed = false;
            }
        }
    }

    /**
     * Creates the new array with enough space to handle the new heap contents
     */
    private void _rebuildHeap() {
        int temp[] = new int[heap.length * 2];
        for (int i = 0; i < heap.length; ++i) {
            temp[i] = heap[i];
        }
        heap = temp;
    }

    /**
     * Extracts the root of the heap replacing it with the new minimum element
     * in the heap
     *
     * @return the minimum element in the heap
     */
    public int extract() {
        if (isEmpty()) {
            throw new IllegalAccessError("Heap is empty");
        }
        heap[0] = heap[1];
        heap[1] = heap[index];
        --index;
        bubbleDown();
        return heap[0];
    }

    private void bubbleDown() {
        boolean change = true;
        int temp_index = 1;
        while (change && temp_index <= index) {
            int left_child = temp_index * 2, right_child = temp_index * 2 + 1;
            int small_index = (heap[left_child] < heap[right_child]) ? left_child : right_child;//here we have the smallest of the two children
            if (heap[small_index] < heap[temp_index]) {
                swap(temp_index, small_index);
                temp_index = small_index;
            } else {
                change = false;
            }
        }
    }

    public int peek() {
        if(isEmpty())
            throw new IllegalAccessError("heap is empty");
        return heap[1];
    }

    public boolean isEmpty(){
        return index ==0;
    }
    public static BinaryHeap of(int... list) {
        BinaryHeap temp = new BinaryHeap(list.length);
        for (int i : list) {
            temp.insert(i);
        }
        return temp;
    }
}