Min & Max Heap Implementation using Java!

Min & Max Heap Implementation using Java!

Implementing Min-Heap and Max-Heap in Java with Step-by-Step Complexity Analysis

Heaps are one of the most important data structures in computer science. They power priority queues, scheduling algorithms, and are the backbone of heap sort.

In this article, we’ll implement MaxHeap and MinHeap from scratch in Java, and analyze time and space complexity line by line.

What is a Heap?

1. A Heap is a complete binary tree stored in an array.

2. MaxHeap → Parent is always greater than or equal to children.

3. MinHeap → Parent is always smaller than or equal to children.

Why use Heaps?

Insert (add): O(log n)

Delete (extract root): O(log n)

Peek (get root): O(1)

Efficient and predictable.

MaxHeap Implementation in Java

public class MaxHeap {

    private int[] heap;
    private int size;

    public MaxHeap() {
        this(16);
    }

    public MaxHeap(int size) {
        if (size < 1) {
            size = 1;
        }
        this.heap = new int[size];
        this.size = 0;
    }

    public void add(int data) {
        grow();
        this.heap[this.size] = data;
        siftUp(this.heap, this.size);
        this.size++;
    }

    public int delete() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int max = this.heap[0];
        int last = this.heap[this.size - 1];
        this.size--;
        if (this.size > 0) {
            this.heap[0] = last;
            this.shiftDown(0, size);
        }
        return max;
    }

    private void siftUp(int[] heap, int index) {
        int i = index;
        int temp = heap[index];
        while (i > 0 && temp > heap[(i - 1) / 2]) {
            heap[i] = heap[(i - 1) / 2];
            i = (i - 1) / 2;
        }
        heap[i] = temp;
    }

    private void shiftDown(int i, int size) {
        while (true) {
            int leftChild = 2 * i + 1;
            int rightChild = 2 * i + 2;
            if (leftChild >= size) {
                return;
            }
            int largest = leftChild;
            if (rightChild < size && this.heap[rightChild] > this.heap[leftChild]) {
                largest = rightChild;
            }
            if (this.heap[i] >= this.heap[largest]) {
                return;
            }
            int temp = this.heap[i];
            this.heap[i] = this.heap[largest];
            this.heap[largest] = temp;
            i = largest;
        }
    }

    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        return this.heap[0];
    }

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

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

    public void clear() {
        this.size = 0;
    }

    private void grow() {
        if (this.size == this.heap.length) {
            this.heap = Arrays.copyOf(this.heap, this.heap.length + 1);
        }
    }

    public int[] toArray() {
        return Arrays.copyOf(this.heap, this.size);
    }

    public static void main(String[] args) {
        MaxHeap heap = new MaxHeap(2);
        heap.add(10);
        heap.add(20);
        heap.add(50);
        heap.add(30);
        heap.add(20);
        System.out.println("Heap: " + Arrays.toString(heap.toArray()));
        System.out.println("Max (peek): " + heap.peek());
        System.out.println("Heap Size: " + heap.size());

        System.out.println("Deleted max: " + heap.delete());
        System.out.println("After delete: " + Arrays.toString(heap.toArray()));
        System.out.println("After delete, Heap Size: " + heap.size());
    }
}

MinHeap Implementation in Java

public class MinHeap {

    private int[] heap;
    private int size;

    public MinHeap() {
        this(16);
    }

    public MinHeap(int size) {
        if (size < 1) {
            size = 1;
        }
        this.heap = new int[size];
        this.size = 0;
    }

    public void add(int data) {
        grow();
        this.heap[this.size] = data;
        siftUp(this.heap, this.size);
        this.size++;
    }

    public int delete() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int min = this.heap[0];
        int last = this.heap[this.size - 1];
        this.size--;
        if (this.size > 0) {
            this.heap[0] = last;
            this.shiftDown(0, size);
        }
        return min;
    }

    private void siftUp(int[] heap, int index) {
        int i = index;
        int temp = heap[index];
        while (i > 0 && temp < heap[(i - 1) / 2]) {
            heap[i] = heap[(i - 1) / 2];
            i = (i - 1) / 2;
        }
        heap[i] = temp;
    }

    private void shiftDown(int i, int size) {
        while (true) {
            int leftChild = 2 * i + 1;
            int rightChild = 2 * i + 2;
            if (leftChild >= size) {
                return;
            }
            int smallest = leftChild;
            if (rightChild < size && this.heap[rightChild] < this.heap[leftChild]) {
                smallest = rightChild;
            }
            if (this.heap[i] <= this.heap[smallest]) {
                return;
            }
            int temp = this.heap[i];
            this.heap[i] = this.heap[smallest];
            this.heap[smallest] = temp;
            i = smallest;
        }
    }

    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        return this.heap[0];
    }

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

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

    public void clear() {
        this.size = 0;
    }

    private void grow() {
        if (this.size == this.heap.length) {
            this.heap = Arrays.copyOf(this.heap, this.heap.length + 1);
        }
    }

    public int[] toArray() {
        return Arrays.copyOf(this.heap, this.size);
    }

    public static void main(String[] args) {
        MinHeap heap = new MinHeap(2);
        heap.add(10);
        heap.add(20);
        heap.add(5);
        heap.add(30);
        heap.add(15);

        System.out.println("Heap: " + Arrays.toString(heap.toArray()));
        System.out.println("Min (peek): " + heap.peek());
        System.out.println("Heap Size: " + heap.size());

        System.out.println("Deleted min: " + heap.delete());
        System.out.println("After delete: " + Arrays.toString(heap.toArray()));
        System.out.println("After delete, Heap Size: " + heap.size());
    }
}

Time & Space Complexity Analysis Step by Step

Max Heap Complexity Analysis

Let’s define: 
n = current heap size
h = ⌊log₂ n⌋ (heap height)
m = old capacity when resizing

---------------------------------------------------
private int[] heap; ----------> O(1)
--> Reference variable only; no allocation here.

private int size; ----------> O(1)
--> Stores current element count; constant-time field.

---------------------------------------------------
public MaxHeap() { ----------> O(1)
    this(16); ----------> O(1)
}
--> Delegates to the size-based constructor; no loop or allocation here.

Total Time Complexity = 1 + 1 = 2 ≈ O(1)
Total Space Complexity = O(1)

---------------------------------------------------
public MaxHeap(int size) { ----------> O(1)
    if (size < 1) { ----------> O(1)
        size = 1; ----------> O(1)
    }
    this.heap = new int[size]; ----------> O(size) zero-initialize
    this.size = 0; ----------> O(1)
}
--> Allocates the backing array; Java zero-fills it.

Total Time Complexity = 1 + 1 + 1 + size + 1 = size + 4 ≈ O(size)
Total Space Complexity = size + 1 ≈ O(size)

---------------------------------------------------
public void add(int data) {
    grow(); ----------> O(1) if not full; O(m) if resize (copy m)
    this.heap[this.size] = data; ----------> O(1)
    siftUp(this.heap, this.size); ----------> O(log n)
    this.size++; ----------> O(1)
}
--> Insert at end, then restore heap-order upwards.

Total Time Complexity (no resize) = 1 + 1 + h + 1 = h + 3 ≈ O(log n)
Total Time Complexity (with resize) = m + 1 + h + 1 = m + h + 2 ≈ O(m + log n)
Total Space Complexity = O(1) normally; O(m) transient during resize

---------------------------------------------------
public int delete() {
    if (size == 0) { ----------> O(1)
        throw new IllegalStateException("Heap is empty"); ----------> O(1)
    }
    int max = this.heap[0]; ----------> O(1)
    int last = this.heap[this.size - 1]; ----------> O(1)
    this.size--; ----------> O(1)
    if (this.size > 0) { ----------> O(1)
        this.heap[0] = last; ----------> O(1)
        this.shiftDown(0, size); ----------> O(log n)
    }
    return max; ----------> O(1)
}
--> Swap root with last, shrink, then restore heap-order downwards.

Total Time Complexity = 1 + 1 + 1 + 1 + 1 + 1 + h + 1 = h + 7 ≈ O(log n)
Total Space Complexity = O(1)

---------------------------------------------------
private void siftUp(int[] heap, int index) {
    int i = index; ----------> O(1)
    int temp = heap[index]; ----------> O(1)
    while (i > 0 && temp > heap[(i - 1) / 2]) { ----------> O(h) iterations
        heap[i] = heap[(i - 1) / 2]; ----------> O(1) per iteration
        i = (i - 1) / 2; ----------> O(1) per iteration
    }
    heap[i] = temp; ----------> O(1)
}
--> Per level, bubble temp up until heap-order holds.

Total Time Complexity = 1 + 1 + (2h) + 1 = 2h + 3 ≈ O(log n)
Total Space Complexity = O(1)

---------------------------------------------------
private void shiftDown(int i, int size) {
    while (true) { ----------> O(h) iterations
        int leftChild = 2 * i + 1; ----------> O(1)
        int rightChild = 2 * i + 2; ----------> O(1)
        if (leftChild >= size) { ----------> O(1)
            return; ----------> O(1)
        }
        int largest = leftChild; ----------> O(1)
        if (rightChild < size && this.heap[rightChild] > this.heap[leftChild]) {
            largest = rightChild; ----------> O(1)
        }
        if (this.heap[i] >= this.heap[largest]) { ----------> O(1)
            return; ----------> O(1)
        }
        int temp = this.heap[i]; ----------> O(1)
        this.heap[i] = this.heap[largest]; ----------> O(1)
        this.heap[largest] = temp; ----------> O(1)
        i = largest; ----------> O(1)
    }
}
--> Compare with children, swap with larger child, move down level by level.

Total Time Complexity = c·h ≈ O(log n)
Total Space Complexity = O(1)

---------------------------------------------------
public int peek() {
    if (size == 0) { ----------> O(1)
        throw new IllegalStateException("Heap is empty"); ----------> O(1)
    }
    return this.heap[0]; ----------> O(1)
}
--> Read root if not empty.

Total Time Complexity = 1 + 1 + 1 = 3 ≈ O(1)
Total Space Complexity = O(1)

---------------------------------------------------
public int size() {
    return this.size; ----------> O(1)
}
--> Direct field access.

Total Time Complexity = 1 ≈ O(1)
Total Space Complexity = O(1)

---------------------------------------------------
public boolean isEmpty() {
    return this.size == 0; ----------> O(1)
}
--> Comparison only.

Total Time Complexity = 1 ≈ O(1)
Total Space Complexity = O(1)

---------------------------------------------------
public void clear() {
    this.size = 0; ----------> O(1)
}
--> Logical clear; capacity unchanged.

Total Time Complexity = 1 ≈ O(1)
Total Space Complexity = O(1)

---------------------------------------------------
private void grow() {
    if (this.size == this.heap.length) { ----------> O(1)
        this.heap = Arrays.copyOf(this.heap, this.heap.length + 1); ----------> O(m) time, O(m) extra space (new array), where m = old length
    }
}
--> Capacity check; allocate/copy only when full.

Total Time Complexity = 1 (check) → O(1) if not full; O(m) if resize
Total Space Complexity = O(1) normally; O(m) transient during resize

---------------------------------------------------
public int[] toArray() {
    return Arrays.copyOf(this.heap, this.size); ----------> O(n) copy
}
--> Returns a fresh array of current size.

Total Time Complexity = n ≈ O(n)
Total Space Complexity = n ≈ O(n)

---------------------------------------------------
Final Summary:

- add: O(log n) amortized without resize; O(m + log n) when resize occurs
- delete: O(log n)
- peek / size / isEmpty / clear: O(1)
- toArray: O(n)
- siftUp / shiftDown: O(log n)
- grow: O(1) when not full; O(m) on resize
- constructor with capacity: O(size) due to allocation and zero-init

Min Heap Complexity Analysis

Lets define: 
n = current heap size
h = ⌊log₂ n⌋ (heap height)
m = old capacity when resizing

---------------------------------------------------
private int[] heap; ----------> Time: O(1)  Space: O(1) (ref)
--> Reference variable only; no allocation here.

private int size; ----------> Time: O(1)  Space: O(1)
--> Stores current element count; constant-time field.

---------------------------------------------------
public MinHeap() { ----------> Time: O(1)  Space: O(1)
    this(16); ----------> Time: O(1)  Space: O(1)
}
Total Time = 1 + 1 = 2 → O(1)
Total Space = O(1) (delegates to next ctor)

---------------------------------------------------
public MinHeap(int size) { ----------> Time: O(1)  Space: O(1)
    if (size < 1) { ----------> Time: O(1)  Space: O(1)
        size = 1; ----------> Time: O(1)  Space: O(1)
    }
    this.heap = new int[size]; ----------> Time: O(size) zero-init; Extra Space: O(size)
    this.size = 0; ----------> Time: O(1)  Space: O(1)
}
Total Time = size + 4 → O(size)
Total Space = O(size)

---------------------------------------------------
public void add(int data) {
    grow(); ----------> O(1) if not full; O(m) if resize (copy m)
    this.heap[this.size] = data;  ----------> O(1)
    siftUp(this.heap, this.size); ----------> O(log n)  // min-heap: bubble up while child < parent
    this.size++; ----------> O(1)
}
Total Time (no resize)  = 1 + 1 + (≈2h+2) + 1 = 2h + 5 → O(log n)
Total Time (with resize)= (m+1) + 1 + (≈2h+2) + 1 = m + 2h + 5 → O(m + log n)
Total Space = O(1) normally; O(m) transient on resize

---------------------------------------------------
public int delete() {
    if (size == 0) {  ----------> O(1)
        throw new IllegalStateException("Heap is empty"); ----------> O(1)
    }
    int min = this.heap[0];  ----------> O(1)
    int last = this.heap[this.size - 1]; ----------> O(1)
    this.size--; ----------> O(1)
    if (this.size > 0) { ----------> O(1)
        this.heap[0] = last; ----------> O(1)
        this.shiftDown(0, size);----------> O(log n)  // min-heap: push down while parent > smaller child
    }
    return min;  ----------> O(1)
}

Empty: 1 + throw → O(1)
Becomes zero after --: ~6 ops → O(1)
Still >0: ~ (1+1+1+1+1+1) + O(log n) + 1 ≈ O(log n)
Total Time (non-empty general) ≈ log n + 6 → O(log n)
Total Space = O(1)

---------------------------------------------------
private void siftUp(int[] heap, int index) {
    int i = index; ----------> O(1)
    int temp = heap[index]; ----------> O(1)
    while (i > 0 && temp < heap[(i - 1) / 2]) { ----------> O(log n) iterations
        heap[i] = heap[(i - 1) / 2];----------> O(1) per iter
        i = (i - 1) / 2;----------> O(1) per iter
    }
    heap[i] = temp; ----------> O(1)
}
Total Time ≈ 2 + 2*log n + 1 = 2*log n + 3 → O(log n)
Total Space = O(1)

---------------------------------------------------
private void shiftDown(int i, int size) {
    while (true) {   ----------> O(log n) iterations
        int leftChild = 2 * i + 1; ----------> O(1)
        int rightChild = 2 * i + 2; ----------> O(1)
        if (leftChild >= size) { ----------> O(1)
            return;  ----------> O(1)
        }
        int smallest = leftChild; ----------> O(1)
        if (rightChild < size && this.heap[rightChild] < this.heap[leftChild]) {
            smallest = rightChild; ----------> O(1)
        }
        if (this.heap[i] <= this.heap[smallest]) { ----------> O(1)
            return; ----------> O(1)
        }
        int temp = this.heap[i]; ----------> O(1)
        this.heap[i] = this.heap[smallest]; ----------> O(1)
        this.heap[smallest] = temp; ----------> O(1)
        i = smallest; ----------> O(1)
    }
}
Per iteration ≈ 9–10 primitive ops; ~h iterations.
Total Time ≈ 9*log n → O(log n)
Total Space = O(1)

---------------------------------------------------
public int peek() {
    if (size == 0) {  ----------> O(1)
        throw new IllegalStateException("Heap is empty");----------> O(1)
    }
    return this.heap[0]; ----------> O(1)
}
Total Time = 2–3 ops → O(1)
Total Space = O(1)

---------------------------------------------------
public int size() {
    return this.size; ----------> O(1)
}
Total Time = 1 → O(1)
Total Space = O(1)

---------------------------------------------------
public boolean isEmpty() {
    return this.size == 0;  ----------> O(1)
}
Total Time = 1 → O(1)
Total Space = O(1)

---------------------------------------------------
public void clear() {
    this.size = 0; ----------> O(1)
}
Total Time = 1 → O(1)
Total Space = O(1) (capacity unchanged)

---------------------------------------------------
private void grow() {
    if (this.size == this.heap.length) { ----------> O(1)
        this.heap = Arrays.copyOf(this.heap, this.heap.length + 1);
        ----------> Arrays.copyOf: O(m) time, O(m) extra space (new array) where m=old length
    }
}
Total Time = O(1) if not full; O(m) if resize
Total Space = O(1) or O(m) transient during resize

---------------------------------------------------
public int[] toArray() {
    return Arrays.copyOf(this.heap, this.size);  ----------> O(n) copy
}
Total Time = n → O(n)
Total Space = O(n) (new array returned)

---------------------------------------------------
Final Summary:

- add: O(log n) amortized without resize; O(m + log n) when resize occurs
- delete: O(log n)
- peek / size / isEmpty / clear: O(1)
- toArray: O(n)
- siftUp / shiftDown: O(log n)
- grow: O(1) when not full; O(m) on resize
- constructor with capacity: O(size) due to allocation and zero-init

Github Link: https://github.com/arafinsami/dsa-patterns/tree/master/src/main/java/com/dsa/heap