/**

/**
 * Created by LEI_D on 6/21/2017.
 */
public class MinHeap {
    private int[] array;
    private int size;

    public MinHeap(int[] arr) throws Exception {
        if (arr == null || arr.length == 0) {
            throw new IllegalAccessException("input array can not be null or empty");
        }

        this.array = arr;
        size = arr.length;
        heapify();
    }

    public MinHeap(int cap) throws Exception {
        if (cap <= 0) {
            throw new IllegalAccessException("cap can not be <= 0");
        }
        array = new int[cap];
        size = 0;
    }

    private void heapify() {
        for (int i = (size - 2)/ 2; i >= 0; i++) {
            percolateDown(i);
        }
    }

    public boolean isFull() {
        return size == array.length;
    }

    public Integer poll() {
        if (isEmpty()) {
            return null;
        } else {
            return array[0];
        }
    }

    public void offer(int ele) {
        if (size == array.length) {
            int[] newArray = array;
            System.arraycopy(array,0,newArray,0, array.length);
            array = newArray;
        }
        array[size] = ele;
        size++;
        percolateUp(size - 1);
    }

    public int update(int index, int ele) {
        try {
            int result = array[index];
            array[index] = ele;
            if (result > ele) {
                percolateUp(index);
            } else {
                percolateDown(index);
            }
            return result;
        } catch (IndexOutOfBoundsException e) {
            throw new IndexOutOfBoundsException("index out of bound");
        }
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private void percolateUp(int index) {
        while(index > 0) {
            int parentIndex = (index - 1) / 2;
            if (array[parentIndex] > array[index]) {
                swap(array, index, parentIndex);
            } else {
                break;
            }
            index = parentIndex;
        }
    }

    private void percolateDown(int index) {
        while(index <= (size - 2) / 2) {
            int leftChild = index * 2 + 1;
            int rightChild = index * 2 + 2;
            int swapCandidate = leftChild;
            if (rightChild <= size - 1 && array[rightChild] <= array[leftChild]) {
                swapCandidate = rightChild;
            }

            if (array[index] > array[swapCandidate]) {
                swap(array, index, swapCandidate);
            } else {
                break;
            }
            index = swapCandidate;
        }
    }

    private void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}