Binary Heap

package dev.namtx.datastructures.binaryheap;

import java.util.ArrayList;

public class BinaryHeap {
    ArrayList<Integer> harr;
    int capacity;
    int heapSize;

    public BinaryHeap(int cap) {
        heapSize = 0;
        capacity = cap;
        harr = new ArrayList<>();
    }

    public void insertKey(int k) throws OverflowException {
        if (heapSize == capacity) {
            throw new OverflowException();
        }

        heapSize++;
        int i = heapSize - 1;
        harr.add(i, k);

        while (i != 0 && harr.get(parent(i)) > harr.get(i)) {
            int tmp = harr.get(parent(i));
            harr.set(parent(i), harr.get(i));
            harr.set(i, tmp);

            i = parent(i);
        }
    }

    public void MinHeapify(int i) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int smallest = i;

        if (left < heapSize && harr.get(left) < harr.get(smallest)) {
            smallest = left;
        }

        if (right < heapSize && harr.get(right) < harr.get(smallest)) {
            smallest = right;
        }

        if (smallest != i) {
            int tmp = harr.get(i);
            harr.set(i, harr.get(smallest));
            harr.set(smallest, tmp);

            MinHeapify(smallest);
        }
    }

    public int extractMin() {
        if (heapSize <= 0) {
            return Integer.MAX_VALUE;
        }
        if (heapSize == 1) {
            heapSize--;
            return harr.get(0);
        }

        int root = harr.get(0);
        harr.set(0, harr.get(heapSize -1));
        heapSize--;
        harr.remove(heapSize);
        MinHeapify(0);

        return root;
    }

    public void decreaseKey(int i, int val) {
        harr.set(i, val);

        while (i != 0 && harr.get(i) < harr.get(parent(i))) {
            int tmp = harr.get(i);
            harr.set(i, harr.get(parent(i)));
            harr.set(parent(i), tmp);

            i = parent(i);
        }
    }

    static int parent(int i) {
        return (i - 1) / 2;
    }

    class OverflowException extends Exception {
    }
}

class Main {
    public static void main(String[] args) throws BinaryHeap.OverflowException {
        BinaryHeap binaryHeap = new BinaryHeap(4);
        binaryHeap.insertKey(1);
        binaryHeap.insertKey(5);
        binaryHeap.insertKey(2);
        binaryHeap.insertKey(4);

        System.out.println(binaryHeap.extractMin());

        binaryHeap.decreaseKey(2, -1);
        System.out.println(binaryHeap);

    }
}