CSCI-258-Labs/258/heapLab/IntMinHeap.java

public class IntMinHeap {

    private int[] heap;
    private int size;

    public IntMinHeap(int initialCapacity) {
        heap = new int[initialCapacity];
    }

    public IntMinHeap() {
        this(10);
    }

    public void add(int n) {
        if (size == heap.length) expandHeap();
        heap[size] = n;
        int child = size++;
        int parent = parent(child);
        while (child > 0 && heap[parent] > heap[child]) {
            swap(heap, child, parent);
            child = parent;
            parent = parent(child);
        }
    }

    public void addCountedLoops(int n) {
        if (size == heap.length) expandHeap();
        heap[size] = n;
        int child = size++;
        int parent = parent(child);
        int i = 0;
        while (child > 0 && heap[parent] > heap[child]) {
            swap(heap, child, parent);
            child = parent;
            parent = parent(child);
            i++;
        }

        System.out.println("Loop went " + i + " times");
    }

    public int remove() {
        int top = heap[0];
        heap[0] = heap[--size];
        int parent = 0;
        int child = smallerChild(parent);
        while (child != -1 && heap[parent] > heap[child]) {
            swap(heap, parent, child);
            parent = child;
            child = smallerChild(parent);
        }
        return top;
    }

    private int smallerChild(int parent) {
        int left = leftChild(parent);
        int right = rightChild(parent);
        if (left < size && right < size) return heap[left] < heap[right]
            ? left
            : right;
        else if (left < size) return left;
        else return -1;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        String s = "[";
        for (int i = 0; i < size; i++) s += heap[i] + ", ";
        return s.substring(0, s.length() - 2) + "]";
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private void expandHeap() {
        int[] oldHeap = heap;
        heap = new int[size * 2];
        for (int i = 0; i < size; i++) heap[i] = oldHeap[i];
    }

    private int parent(int child) {
        return (child - 1) / 2;
    }

    private int leftChild(int parent) {
        return parent * 2 + 1;
    }

    private int rightChild(int parent) {
        return parent * 2 + 2;
    }
}