JAVA: Min‐Heap - rFronteddu/general_wiki GitHub Wiki

public class MinHeap {
    private int[] heap;
    private int size;
    private int maxSize;

    public MinHeap(int maxSize) {
        this.maxSize = maxSize;
        this.size = 0;
        this.heap = new int[maxSize + 1];
        this.heap[0] = Integer.MIN_VALUE; // sentinel value to simplify finding parent, left and right child
    }

    private int parent(int pos) { // O(1)
        return pos / 2;
    }

    private int leftChild(int pos) { // O(1)
        return 2 * pos;
    }

    private int rightChild(int pos) { // O(1)
        return 2 * pos + 1;
    }

    // Nodes from size/2 + 1 to size are leaf nodes.
    private boolean isLeaf(int pos) { // O(1)
        return pos > size / 2 && pos <= size;
    }

    private void swap (int fpos, int spos) { // O(1)
        int tmp = heap[fpos];
        heap[fpos] = heap[spos];
        heap[spos] = tmp;
    }

    // each parent node must have a value less than or equal to its children's values.
    // if heap[pos] is bigger, swap with the smallest children
    // follow the branch and verify heapify is verified
    private void heapify (int pos) { // O(log n)
        if (isLeaf (pos)) {
            return;
        }
        int l = leftChild (pos);
        int r = rightChild (pos);

        if(l <= size && (heap[pos] > heap[l] || (r <= size && heap[pos] > heap[r]))) {
            if (r > size || heap[l] < heap[r]) {
                swap (pos, l);
                heapify (l);
            } else {
                swap (pos, r);
                heapify (r);
            }
        }
    }


    public void buildHeap(int[] arr) { // O(n)
        if (arr.length > maxSize) {
            throw new IllegalArgumentException ("Input array size exceeds heap's maximum capacity");
        }

        size = arr.length;
        System.arraycopy(arr, 0, heap, 1, size); // Copy elements to heap array starting from index 1

        // Perform heapify on all non-leaf nodes
        for (int i = size / 2; i >= 1; i--) {
            heapify(i);
        }
    }

    public void insert (int element) { // O(log n)
        if (size >= maxSize) {
            // heap full
            return;
        }

        heap[++size] = element;
        int current = size;
        
        while(heap[current] < heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        } 
    }

    public int remove() { // O(log n), find min is O(1)
        // remove and return min
        int popped = heap[1];
        heap[1] = heap[size--];
        heapify(1);
        return popped;
    }

    public void print() {
        for(int i = 1; i <= size / 2; i++) {
            // parent: heap[i] + " left child: " + heap[2 * i] + " right child: " + heap[2 * i + 1]
        }
    }
}