☕ DSA Java Articles

Topics › Heaps › Learning

Implement Max Heap

Medium TUF ID 575 SDE

Java source ↗ Edit this article ↗

Problem

Implement a max heap of integers from scratch, without java.util.PriorityQueue. It must support:

A useful extra, covered below, is building a heap from an existing array in linear time.

Constraints: up to 10^5 operations, values fit in an int, duplicates allowed. The judge only calls getMax and extractMax on a non-empty heap; the code here throws NoSuchElementException on an empty heap so misuse is loud rather than silent.

Example 1

insert(5), insert(3), insert(8), getMax(), insert(10), heapSize(), extractMax(), extractMax(), getMax()
output: 8, 4, 10, 8, 5        // the largest element always comes out first

Example 2

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

Both implementations satisfy one interface, so a single test script drives them and compares them with PriorityQueue as an oracle:

interface MaxHeapOps {
    void insert(int key);
    int getMax();
    int extractMax();
    void changeKey(int index, int newVal);
    boolean isEmpty();
    int heapSize();
}

Approach 1: Brute force, unsorted array

Intuition. The simplest container for a multiset is a growable array with a size counter. Insertion appends in O(1). All the cost moves to the queries: the elements are in no particular order, so finding the maximum means scanning everything. Removal is cheap once the maximum is found, because order does not matter: copy the last element into the hole and shrink the size.

Algorithm.

  1. insert: double the array if full, then write the key at size and increment size.
  2. getMax: scan indices 0..size-1 for the largest value.
  3. extractMax: find the index of the maximum, remember its value, overwrite it with the last element, decrement size.
  4. changeKey: overwrite the slot; no ordering exists to repair.
static class UnsortedArrayHeap implements MaxHeapOps {
    private int[] data = new int[8];
    private int size = 0;

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

    private int maxIndex() {
        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 getMax() {
        return data[maxIndex()];
    }

    public int extractMax() {
        int i = maxIndex();
        int max = data[i];
        data[i] = data[--size];                        // order is irrelevant: fill the hole with the last element
        return max;
    }

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

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

    public int heapSize() {
        return size;
    }
}

Complexity. insert and changeKey are O(1) (amortised for the doubling). getMax and extractMax are O(n). Space O(n). A workload that alternates inserts and extracts costs O(n^2) overall, which is what a heap is designed to avoid.

Approach 2: Optimal, binary max-heap in an array

Intuition. A binary max-heap is a complete binary tree in which every node is at least as large as its children. “Complete” means every level is full except possibly the last, which fills from the left. That shape lets us store the tree level by level in an array with no pointers:

The order rule chains along every root-to-leaf path, so the root heap[0] is the maximum. A complete tree with n nodes has height floor(log2 n), and every update below repairs the order along a single path, so each costs O(log n).

Two repair moves do all the work:

Algorithm.

  1. insert: place the key at the first free slot (the next leaf), then sift it up.
  2. getMax: return heap[0].
  3. extractMax: save heap[0], move the last leaf into the root, shrink the size, sift the root down.
  4. changeKey: overwrite the slot. If the value grew, it can only violate the rule with its parent, so sift up; if it shrank, it can only violate it with its children, so sift down.
  5. Build from an array: copy the values, then sift down every internal node from the last one (size / 2 - 1) back to the root.
static class BinaryMaxHeap implements MaxHeapOps {
    private int[] heap;
    private int size;

    BinaryMaxHeap() {
        heap = new int[8];
    }

    /** Builds a heap from arbitrary values in O(n) by sifting down every internal node, last one first. */
    BinaryMaxHeap(int[] values) {
        heap = Arrays.copyOf(values, Math.max(8, values.length));
        size = values.length;
        for (int i = size / 2 - 1; i >= 0; i--) siftDown(i);
    }

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

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

    public int extractMax() {
        if (size == 0) throw new NoSuchElementException("heap is empty");
        int max = heap[0];
        heap[0] = heap[--size];                        // move the last leaf to the root
        siftDown(0);                                   // and let it sink to its place
        return max;
    }

    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);               // bigger: may beat its parent
        else siftDown(index);                          // smaller: may lose to a child
    }

    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(p, i);
            i = p;
        }
    }

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

    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);
    }
}

snapshot() exposes the array for the tests, which check the exact layouts in Example 2 and the heap property after random changeKey calls.

Dry run: insert 5, 3, 8, 10, then extractMax().

step array after the step what happened
insert 5 [5] root
insert 3 [5, 3] 3 ≤ parent 5, stays
insert 8 [8, 3, 5] 8 > parent 5 at index 0, swap
insert 10 [10, 8, 5, 3] 10 swaps with 3 (index 1), then with 8 (index 0)
extractMax → 10 [8, 3, 5] last leaf 3 moves to the root, swaps with larger child 8

Why building is O(n) and not O(n log n). Inserting n values one by one costs O(n log n). Bottom-up building is cheaper because most nodes are near the bottom: about n/2 nodes are leaves and need no work, about n/4 sit one level up and sift down at most one level, about n/8 at most two levels, and so on. The total is n · (1/4 + 2/8 + 3/16 + ...), which is at most n. Leaves are skipped entirely by starting at index size / 2 - 1, the last node that has a child.

Complexity. insert, extractMax and changeKey are O(log n); getMax, isEmpty and heapSize are O(1); building from an array is O(n). Space O(n) for the array, which doubles when full so insertion stays amortised O(log n).

Edge cases and pitfalls