MyCustomHeap.java

package warmup;

public class MyCustomHeap {
    int[] mHeap;
    int mSize;

    public MyCustomHeap(int capacity) {
        mSize = 0;
        mHeap = new int[capacity];
    }

    private int Parent(int i) {
        return (i-1)/2;
    }

    private int Left(int i) {
        return 2*i+1;
    }

    private int Right(int i) {
        return 2*i+2;
    }


    private void swap(int a, int b) {
        int temp = mHeap[a];
        mHeap[a] = mHeap[b];
        mHeap[b] = temp;
        //System.out.println("a=" + a);
        //System.out.println("b=" + b);
    }

    private void Heapify(int i) {
        int l = Left(i);
        int r = Right(i);
        int min = i;
        if (l < mSize && mHeap[l] < mHeap[i]) {
            min = l;
        }
        if (r < mSize && mHeap[r] < mHeap[min]) {
            min = r;
        }
        if (min != i) {
            swap(i, min);
            Heapify(min);
        }
    }

    private void DecreaseKey(int i, int value) {
        mHeap[i] = value;
        while (i != 0 && mHeap[i] < mHeap[Parent(i)]) {
            swap(i, Parent(i));
            i = Parent(i);
        }
    }

    public void Insert(int value) {
        mSize++;
        int i = mSize -1;
        mHeap[i] = value;

        while(i !=0 && mHeap[Parent(i)] > mHeap[i]) {
            swap(Parent(i), i);
            i = Parent(i);
        }
    }

    public int ExtractMin() {
        if (mSize <= 0) {
            return Integer.MIN_VALUE;
        }
        if (mSize == 1) {
            mSize--;
            return mHeap[0];
        }
        int root = mHeap[0];
        mHeap[0] = mHeap[mSize-1];
        mSize--;
        Heapify(0);

        return root;
    }

    public int GetMin() {
        return mHeap[0];
    }

    public void Delete(int i) {
        DecreaseKey(i, Integer.MIN_VALUE);
        ExtractMin();
    }

    public String ToString() {
        StringBuilder sb = new StringBuilder();
        for (int i =0; i < mSize; i++) {
            sb.append(mHeap[i]);
            sb.append(" ");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        MyCustomHeap h = new MyCustomHeap(20);
        h.Insert(3);
        h.Insert(2);
        assert h.GetMin() == 2 : "minimum is not 2";
        h.Delete(1);
        h.Insert(15);
        h.Insert(5);
        h.Insert(4);
        h.Insert(45);
        System.out.println(h.ToString());;
        assert h.ExtractMin() == 2;

        assert h.GetMin() == 4;
        h.DecreaseKey(2, 1);
        assert h.GetMin() == 1;

    }

}