Heap Operations

A binary heap keeps only one invariant — every parent obeys an order relation with its children — and enforces it locally after each mutation by bubbling the disturbed element up or down the tree, which is what lets insert and extract-root run in logarithmic time on an array with no pointers.

Recognize the pattern

• You repeatedly need the current min/max from a changing collection ("top-k", "k closest", "merge k sorted lists", "median so far", "schedule by earliest deadline").
• You don't need full sorted order, only ordered access to the extreme element, one at a time.
• Elements arrive over time (streaming) rather than all at once — a rule that pushes you toward a heap instead of resorting an array.

Brute force vs. optimal

The heap is the sweet spot: it never pays O(n) for insert or extract because it only restores order along a single root-to-leaf path, never the whole array.

Complexity, derived

Store the heap in an array; for index i, children are 2i+1, 2i+2 and parent is (i-1)/2. A complete binary tree of n nodes has height h = floor(log2 n).

Insert (heapify-up): append at index n (O(1) amortized for the array), then compare-and-swap with the parent at most once per level. Number of levels climbed ≤ h = O(log n), each step is O(1) work → total O(log n) time. Extra space: no recursion needed (iterative loop), so O(1) auxiliary space beyond the array itself.

Extract-root (heapify-down): move the last element to the root (O(1)), then at each level compare against up to 2 children and swap with the larger/smaller. Again bounded by height h → O(log n) time, O(1) auxiliary space.

Build-heap from n elements (not naive n inserts): calling heapify-down on all internal nodes bottom-up costs Σ (n / 2^(h+1)) · h summed over levels, which converges to O(n), not O(n log n) — because most nodes are near the bottom and sink only a short distance.

Traced example — inserting 2 into a Min-Heap

Heap array before insert: [3, 5, 4, 8, 9] (indices 0..4).

Final heap: [2,5,3,8,9,4], valid Min-Heap in 2 swaps ≈ height (log2 6 ≈ 2.58).

Step through push and pop

The debugger below builds a min-heap by inserting values one at a time (each sifts up from the last slot), then does one extract-min (root leaves, the last element drops to the root and sifts down). Watch the array and the complete tree stay in lock-step; at each comparison, predict whether to swap or stop.

Java: array-backed min-heap core

class MinHeap {
    private int[] a;
    private int size = 0;

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

    void insert(int val) {
        a[size] = val;
        int i = size++;
        while (i > 0 && a[(i - 1) / 2] > a[i]) {
            int parent = (i - 1) / 2;
            int tmp = a[i]; a[i] = a[parent]; a[parent] = tmp;
            i = parent;
        }
    }

    int extractMin() {
        int min = a[0];
        a[0] = a[--size];
        heapifyDown(0);
        return min;
    }

    // iterative on purpose: a recursive version costs O(log n) call stack,
    // which would contradict the O(1) auxiliary-space claim above
    private void heapifyDown(int i) {
        while (true) {
            int smallest = i, l = 2 * i + 1, r = 2 * i + 2;
            if (l < size && a[l] < a[smallest]) smallest = l;
            if (r < size && a[r] < a[smallest]) smallest = r;
            if (smallest == i) break;
            int tmp = a[i]; a[i] = a[smallest]; a[smallest] = tmp;
            i = smallest;
        }
    }
}

Standard Library PriorityQueue remove() Trap & Indexed Heaps

Standard libraries (like Java's java.util.PriorityQueue) store heaps as a flat array. They do not maintain a mapping from an element to its current index in the array. This creates a critical performance trap:

• The O(N) Search & Removal Trap: While peeking at the minimum is O(1) and popping is O(log N), updating or removing an arbitrary element (e.g. calling pq.remove(element) or checking pq.contains(element)) requires a linear scan of the underlying array to find the element before heapifying. This makes the operation O(N) linear time.
• Impact on Dijkstra: In Dijkstra's or Prim's algorithm, when you find a shorter path to a vertex already in the queue, you must update its priority. A naive implementation that calls pq.remove(u) and then re-inserts u will run in O(E·V) rather than the optimal O(E log V). On graphs with millions of edges, this performance degradation is catastrophic.
• The Interview-Friendly Solution (Lazy Deletion): Instead of updating priorities in-place, you can simply insert a duplicate entry (new_distance, u) into the priority queue. In the outer Dijkstra loop, when you pop a node, check if it has already been visited (i.e. if (visited[node]) continue;). If so, discard it. This avoids calling remove(), keeping the time complexity at O(E log V) at the cost of using at most O(E) auxiliary space for duplicates.
• The Production Solution (Indexed Priority Queue): For space-sensitive or large-scale systems, duplicate entries are unacceptable. A production-grade heap maintains an auxiliary index map (such as Map<Element, Integer> elementToIndex) alongside the heap array. When swapping two elements in the heap array, you also update their positions in the map. This allows you to find any element's array index in O(1) time, making decreaseKey(element, new_priority) a true O(log N) operation while keeping space at O(V). (In theory a Fibonacci heap makes decrease-key amortized O(1), but its constants and implementation complexity keep binary/indexed heaps the practical default.)

Pitfalls

• Using PriorityQueue<> in Java (min-heap by default) but expecting a max-heap — you must pass Collections.reverseOrder() or negate keys.
• Calling remove(Object) or contains(Object) on standard libraries' heaps, which takes O(N) time and degrades Dijkstra/Prim to O(V·E) when updates are frequent.
• Off-by-one in parent/child index formulas when the heap is 1-indexed vs 0-indexed — mixing the two conventions silently corrupts the structure.
• Calling heapify-down without checking whether the right child exists (it may be absent even when the left child is present) — causes an out-of-bounds read or wrong comparison.
• Assuming a heap is sorted — it is only weakly ordered; siblings and cousins have no defined order, so in-order traversal is not sorted output.

When to use / when not

Use a heap when you need repeated access to a running min/max with online insertions (Dijkstra's frontier, top-k streaming, scheduling by priority). Avoid it when you need to search for an arbitrary element (O(n), no better than a list) or need full sorted order repeatedly (sort once, O(n log n), instead of extracting one-by-one for O(n log n) anyway but with more constant overhead and no random access).

Takeaways

• Heap operations are all bounded by tree height O(log n) because each fixup touches one root-to-leaf path, not the whole array.
• Build-heap is O(n), not O(n log n) — bottom-up heapify exploits that most nodes are near the leaves.
• A heap gives fast access to the extreme element only; it is not a substitute for a sorted structure or a search index.

Recall: Why does building a heap from n elements bottom-up take O(n) time instead of O(n log n)?

Source: heap fundamentals as commonly taught in CLRS (Introduction to Algorithms) Ch. 6, cross-checked against the current page's insert/delete algorithm description.