Introduction to Heap

A heap works by enforcing one weak invariant — every parent dominates its children (≥ for max-heap, ≤ for min-heap) — on top of a shape invariant (complete binary tree), which together let it live in a plain array with no pointers and guarantee the extreme element is always at index 0, while insert/remove only need to fix a single root-to-leaf path rather than re-sort anything.

Recognize the pattern

• Problem asks for repeated access to the current min/max while the set keeps changing ("k largest so far", "running median", "next earliest event").
• You need a priority queue: process items by priority, not insertion order (Dijkstra, task scheduling, merge k sorted lists).
• You only ever need the top-1 element fast, not the full sorted order — sorting everything would be wasted work.
• Keywords: "top-k", "k-th largest/smallest", "nearest k points", "merge k lists".

Brute force → optimal

Brute force A (unsorted array): insert is O(1) append, but find-min/max scans everything: O(n) per query.

Brute force B (fully sorted array): find-min is O(1), but insert costs O(n) to shift elements into place. You've just moved the cost, not removed it.

Optimal (heap): accept a weaker order — only parent–child, never sibling–sibling. This buys O(1) peek and O(log n) insert/remove, because restoring the invariant only ever touches one root-to-leaf path, never the whole array.

Array representation

A heap is stored via level-order (BFS) traversal in an array — no pointers needed. For a node at index i: left child is at 2i+1, right child at 2i+2, parent at (i-1)/2 (integer division). Because the tree is always complete, these formulas always land on a valid, contiguous slot — that's the whole trick that makes arrays work here.

Complexity from first principles

Height: a complete binary tree with n nodes has height h = ⌊log₂ n⌋, because each level doubles the node count and the array packs levels contiguously with no gaps.

Insert (sift-up): the new element starts at a leaf and, in the worst case, swaps once per level on the way to the root. Number of comparisons/swaps ≤ h = O(log n). Peek: O(1) — it's just array[0].

Extract-min/max (sift-down): move the last element to the root (O(1)), then at each of h levels compare with (up to) 2 children and swap with the larger/smaller one: O(1) work × h levels = O(log n).

Build-heap from n elements: naive "insert n times" gives O(n log n). But bottom-up heapify (sift-down starting from the last internal node) is O(n): most nodes are near the bottom where sift-down does almost no work; summing cost×count over levels gives ∑ n/2^(h+1) · h = O(n), not O(n log n).

Space: O(n) for the array, O(1) extra for insert/extract (in-place swaps), O(log n) if sift-down/up is written recursively (call stack) — use the iterative form to keep it O(1).

Worked example: inserting 5 into a max-heap

Heap array: [16,14,10,8,7,9,3]. Insert 5 at the end, then sift up.

Now extract-max on [16,14,10,8,7,9,3]:

public class MinHeap {
    private int[] a;
    private int size;

    public MinHeap(int capacity) { a = new int[capacity]; size = 0; }

    public int peek() {
        if (size == 0) throw new java.util.NoSuchElementException("heap is empty");
        return a[0];
    }

    public void insert(int val) {
        a[size] = val;
        int i = size++;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (a[parent] <= a[i]) break;
            swap(parent, i);
            i = parent;
        }
    }

    public int extractMin() {
        if (size == 0) throw new java.util.NoSuchElementException("heap is empty");
        int min = a[0];
        a[0] = a[--size];
        siftDown(0);
        return min;
    }

    private void siftDown(int i) {
        while (true) {
            int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
            if (left < size && a[left] < a[smallest]) smallest = left;
            if (right < size && a[right] < a[smallest]) smallest = right;
            if (smallest == i) break;
            swap(i, smallest);
            i = smallest;
        }
    }

    private void swap(int x, int y) { int t = a[x]; a[x] = a[y]; a[y] = t; }
}

Pitfalls

• Unguarded peek/extract on an empty heap — without an explicit size check, extract decrements size to -1 and corrupts the heap's state (or reads garbage); throw NoSuchElementException instead of failing dirty.
• Forgetting to move the last element to the root before sift-down during extraction — using the wrong element corrupts the heap silently.
• Using (i-1)/2 in a language with floor-toward-negative-infinity division on negative numbers, or forgetting integer division truncates — off-by-one parent lookups.
• Assuming a heap is sorted: iterating the array in index order does not give sorted output; only repeated extraction does.
• Recursive sift-up/down blowing the stack or adding hidden O(log n) space on very large heaps — prefer iterative.
• Comparator bugs in language built-ins (e.g., Java's PriorityQueue is a min-heap by default; forgetting to pass Collections.reverseOrder() for max-heap behavior).

When to use / when NOT — trade-offs

Use a heap when you need fast repeated access to only the current extreme value and don't care about full ordering (priority queues, top-k, Dijkstra) — and note that two heaps back-to-back solve running median: a max-heap of the lower half plus a min-heap of the upper half gives O(log n) insert and O(1) median. Prefer a sorted structure or balanced BST when you need range queries, predecessor/successor lookups, or full sorted traversal — a heap can't do those efficiently since it only orders parent–child, not siblings.

Takeaways

• Heap = complete binary tree + parent-dominance invariant, stored pointer-free in an array via index arithmetic.
• Peek is O(1); insert and extract are O(log n) because they only touch one root-to-leaf path.
• Building a heap from n elements bottom-up is O(n), not O(n log n) — don't insert one-by-one if you have all elements upfront.
• A heap gives you the top element fast but is not a substitute for a sorted structure or a BST when you need ordering beyond the root.

Recall: Why is bottom-up heapify O(n) instead of O(n log n) even though each sift-down is O(log n) in the worst case?

Synthesized from CLRS (Cormen et al., Introduction to Algorithms), Sedgewick & Wayne's Algorithms, and standard heap/priority-queue treatments used in interview-prep references.