☕ DSA Java Articles

Topics › Heaps › Learning

Implement Min Heap

Medium TUF ID 576 A2Z

Java source ↗ Edit this article ↗

Problem

Implement a min heap of integers from scratch, without PriorityQueue. It must support:

Constraints: up to 10^5 operations, values fit in an int. getMin and extractMin are only called on a non-empty heap in the judge’s version; the code here throws NoSuchElementException on an empty heap so misuse is loud. changeKey is defined in terms of the array layout, so its effect depends on where the implementation keeps each element.

Example 1

insert(5), insert(3), insert(8), getMin(), insert(1), heapSize(), extractMin(), extractMin(), getMin()
output: 3, 4, 1, 3, 5          // the minimum always comes out first, whatever the insertion order

Example 2

insert(4), insert(7), insert(9), insert(10)    // heap array is [4, 7, 9, 10]
changeKey(3, 1)                                // 10 becomes 1 and climbs: [1, 4, 9, 7]
changeKey(0, 20)                               // the root becomes 20 and sinks: [4, 7, 9, 20]
getMin() -> 4

Both implementations below satisfy one small interface, so a single test script drives them:

interface MinHeapOps {
    void insert(int key);
    int getMin();
    int extractMin();
    void changeKey(int index, int newVal);
    boolean isEmpty();
    int heapSize();
}

Approach 1: Unsorted array

Intuition. The simplest container that can hold a multiset is an array with a size counter. Insertion just appends. The price is paid when someone asks for the minimum: nothing is ordered, so we must scan everything. Removal is cheap once the minimum is found, because order does not matter: move the last element into the hole and shrink the size.

Algorithm.

  1. Keep data (doubled when full) and size.
  2. insert(key): write data[size++] = key.
  3. getMin(): scan data[0..size-1] for the index of the smallest value and return it.
  4. extractMin(): find that index i, remember data[i], then copy data[size - 1] into slot i and decrement size.
  5. changeKey(i, v): just overwrite data[i], since there is no invariant to repair.
static class UnsortedArrayHeap implements MinHeapOps {
    private int[] data = new int[4];
    private int size = 0;

    public void insert(int key) {
        if (size == data.length) data = Arrays.copyOf(data, size * 2);
        data[size++] = key;
    }

    private int minIndex() {
        if (size == 0) throw new NoSuchElementException("heap is empty");
        int best = 0;
        for (int i = 1; i < size; i++) {
            if (data[i] < data[best]) best = i;
        }
        return best;
    }

    public int getMin() {
        return data[minIndex()];
    }

    public int extractMin() {
        int i = minIndex();
        int min = data[i];
        data[i] = data[--size];          // fill the hole with the last element
        return min;
    }

    public void changeKey(int index, int newVal) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException("index " + index);
        data[index] = newVal;            // there is no order to restore
    }

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

    public int heapSize() {
        return size;
    }
}

Complexity. insert and changeKey are O(1) (amortised for the occasional doubling). getMin and extractMin are O(n) because each scans the whole array. Space O(n).

A workload that alternates inserts and extract-mins, which is exactly how heaps are used in Dijkstra’s algorithm or k-way merging, costs O(n^2) here. Keeping the array fully sorted would just move the cost: getMin becomes O(1) but insert must shift elements, O(n) again. We need a structure that is “sorted enough” to find the minimum instantly, yet cheap to repair.

Approach 2: Binary min-heap

Intuition. A binary heap is a complete binary tree stored level by level in an array, where every node is at most its children. Node i has children 2i + 1 and 2i + 2 and parent (i - 1) / 2. The order rule chains along every root-to-leaf path, so the root heap[0] is the minimum. The tree has height floor(log2 n), and every modification can be repaired by walking a single path up or down, never touching the rest of the tree.

Algorithm.

  1. insert(key): grow the array if full, store at heap[size], increment size, sift up from size - 1.
  2. getMin(): return heap[0].
  3. extractMin(): save heap[0], decrement size, copy heap[size] to heap[0], sift down from 0, return the saved value.
  4. changeKey(i, v): store v; sift up if it decreased, otherwise sift down.
  5. Sift up stops when the parent is <= the node; sift down stops when neither child is smaller.
static class BinaryMinHeap implements MinHeapOps {
    private int[] heap = new int[4];
    private int size = 0;

    public void insert(int key) {
        if (size == heap.length) heap = Arrays.copyOf(heap, size * 2);
        heap[size] = key;
        size++;
        siftUp(size - 1);
    }

    public int getMin() {
        if (size == 0) throw new NoSuchElementException("heap is empty");
        return heap[0];
    }

    public int extractMin() {
        if (size == 0) throw new NoSuchElementException("heap is empty");
        int min = heap[0];
        size--;
        heap[0] = heap[size];            // last leaf becomes the root
        siftDown(0);
        return min;
    }

    public void changeKey(int index, int newVal) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException("index " + index);
        int old = heap[index];
        heap[index] = newVal;
        if (newVal < old) siftUp(index);
        else siftDown(index);
    }

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

    public int heapSize() {
        return size;
    }

    private void siftUp(int i) {
        while (i > 0) {
            int p = (i - 1) / 2;
            if (heap[p] <= heap[i]) break;
            swap(i, p);
            i = p;
        }
    }

    private void siftDown(int i) {
        while (true) {
            int smallest = i, l = 2 * i + 1, r = 2 * i + 2;
            if (l < size && heap[l] < heap[smallest]) smallest = l;
            if (r < size && heap[r] < heap[smallest]) smallest = r;
            if (smallest == i) return;
            swap(i, smallest);
            i = smallest;
        }
    }

    private void swap(int i, int j) {
        int t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }

    int[] snapshot() {
        return Arrays.copyOf(heap, size);
    }
}

Dry run of Example 2 on the binary heap:

operation array before repair repair array after
insert 4, 7, 9, 10 [4, 7, 9, 10] each new key is at least its parent [4, 7, 9, 10]
changeKey(3, 1) [4, 7, 9, 1] 1 < parent 7: swap; 1 < parent 4: swap [1, 4, 9, 7]
changeKey(0, 20) [20, 4, 9, 7] smaller child 4: swap; child 7 < 20: swap [4, 7, 9, 20]
extractMin() → 4 [20, 7, 9] smaller child 7: swap [7, 20, 9]

Complexity. insert, extractMin and changeKey are O(log n): each walks one path of a tree of height floor(log2 n). getMin, isEmpty and heapSize are O(1). Space O(n) for the array, which doubles when full so insertion stays amortised O(log n).

operation unsorted array binary heap
insert O(1) O(log n)
getMin O(n) O(1)
extractMin O(n) O(log n)
changeKey O(1) O(log n)

The tests run a seeded random mix of 4000 inserts and extracts against java.util.PriorityQueue for both implementations, and 300 random changeKey calls on the binary heap, checking the heap property after each one.

Edge cases and pitfalls