Heaps & Priority Queues — Five Problems

A heap is a complete binary tree obeying one ordering rule at every node.

• Min-heap — every parent ≤ both children. The minimum sits at the root.
• Max-heap — every parent ≥ both children. The maximum sits at the root.
• The rule holds recursively for every node, not just the root.
• Root access is O(1); there is no global left-to-right ordering, only the parent/child relation.

Heapify restores the property by swapping a violating node with a parent/child until the rule holds again. On insert, the new node lands at the bottom and "bubbles up" via swaps; on extract, the root is removed and the property is restored downward.

⭐ TRICK — Heapify walks the height, so it's O(log n). A node inserted at the deepest leaf can, worst case, travel all the way to the root — that path length is the tree height, and a binary tree's height is log₂n. Sorting n elements through a heap is therefore n × O(log n) = O(n log n).

💡 TIP — You rarely code heapify by hand. Java's PriorityQueue heapifies internally on every add/poll. Learn the manual process anyway: interviewers ask you to explain it, even though your solution code just calls the library. [+]

PriorityQueue is a min-heap by default. Flip it to a max-heap with a reverse-order comparator.

⚠ PITFALL — the array-index formulas assume 0-based indexing. For a node at index i: left child = 2i+1, right child = 2i+2. If you (or a source) start indexing at 1, the formulas shift to 2i and 2i+1 — a frequent off-by-one bug. [!] The transcript first guessed i+1 / i+2, then corrected to 2i+1 / 2i+2; the corrected form is right.

Given an integer array and a positive integer k (k ≤ n), return the k-th largest element. Not the k largest elements — the single element in the k-th largest position.

Practice: LeetCode 215 — Kth Largest Element in an Arrayleetcode.com/problems/kth-largest-element-in-an-array↗

Brute force: sort descending, return index k−1 → O(n log n). Correct but wasteful — you paid to fully order every element when you only cared about one position.

⭐ TRICK — keep a size-k MIN-heap, not a max-heap. Scan the array; hold only the k largest seen so far. Because it's a min-heap, its root is the smallest of those k — which is exactly the k-th largest overall. For each new element, if it beats the root, poll the root and add it. Heap never exceeds size k, so each operation is O(log k) → total O(n log k).

⚠ PITFALL — the instinctive choice is a max-heap, and it's wrong. A max-heap of all n elements works but costs O(n log n) and an interviewer will ask you to improve it. The min-heap is the answer they want.

public static int findKthLargest(List<Integer> arr, int k) {
    if (arr == null || arr.size() < k) System.exit(-1);   // invalid input

    // min-heap seeded with the first k elements
    PriorityQueue<Integer> pq = new PriorityQueue<>(arr.subList(0, k));

    for (int i = k; i < arr.size(); i++) {
        if (arr.get(i) > pq.peek()) {   // bigger than the smallest of our k
            pq.poll();                  // drop the smallest
            pq.add(arr.get(i));         // keep the new, larger one
        }
    }
    return pq.peek();   // root = k-th largest
}

Time O(n log k) · Space O(k) — auxiliary space is just the heap, which never exceeds k elements (the input list itself is a separate O(n)). Edge cases: arr null or shorter than k (guard up front); duplicates are handled naturally since we compare values.

Array [23,19,46,32,70,10], k=3. After processing, the min-heap holds the three largest {32,46,70} with root 32 → 3rd largest is 32. When 70 arrives it beats root 23, so 23 leaves; when 10 arrives it loses to root 32, so it's ignored.

Why this matters: the "size-k heap" idea powers every top-K problem — top-K frequent elements, k closest points, k largest in a stream. Recognizing "I only need k of them" is the reusable insight.

Given n ropes of different lengths, connect them all into one rope at minimum total cost, where joining two ropes costs the sum of their lengths. Example [5,4,2,8] → cost 36.

Practice: GeeksforGeeks — "Connect n ropes with minimum cost"geeksforgeeks.org/connect-n-ropes-minimum-cost↗. [+] Equivalent to LeetCode 1167 "Minimum Cost to Connect Sticks" (LeetCode Premium).

⭐ TRICK — always merge the two SMALLEST ropes first (Huffman logic). Every time you merge a rope, its length is re-added to future merge costs. So the smallest ropes should be combined earliest to minimize how many times their length gets re-counted. A min-heap hands you the two smallest in O(log n) each.

Algorithm: put all lengths in a min-heap. While size > 1: poll two smallest, sum them, add the sum to a running cost, push the sum back. The sum re-enters as a new "rope." Stop when one rope remains.

⚠ PITFALL — this is "two smallest," not "k smallest." [!] The transcript briefly suggested a max-heap (confusing it with the k-smallest rule). Wrong here: you need the immediate two minimums repeatedly, which is precisely what a min-heap gives. Do not reach for a max-heap.

public static int findMinCost(List<Integer> prices) {
    PriorityQueue<Integer> pq = new PriorityQueue<>(prices);   // min-heap
    int cost = 0;

    while (pq.size() > 1) {
        int x = pq.poll();        // smallest
        int y = pq.poll();        // second smallest
        int sum = x + y;          // cost of this merge
        pq.add(sum);              // merged rope goes back in
        cost += sum;              // accumulate
    }
    return cost;
}

Time O(n log n) · Space O(n). Worked: [5,4,2,8] → merge 2+4=6 → merge 5+6=11 → merge 11+8=19 → total 6+11+19 = 36.

This is Huffman coding in disguise. The same "repeatedly combine the two smallest and feed the result back" structure builds Huffman trees and solves file/optimal-merge problems. Recognizing the pattern lets you reuse the min-heap greedy skeleton verbatim.

Integers arrive one at a time in an unbounded stream; after each arrival, return the k-th largest element seen so far. A design/stateful variant of Problem I.

Practice: LeetCode 703 — Kth Largest Element in a Streamleetcode.com/problems/kth-largest-element-in-a-stream↗

⭐ TRICK — persist the size-k min-heap as object state. Same engine as Problem I, but the heap lives across calls instead of being rebuilt. It permanently holds the k largest; its root is always the current k-th largest, returned in O(1). Each incoming element costs only O(log k).

add(n) logic: if heap size < k, just add n (still filling). Otherwise, if n > root (the smallest of the top k), poll and add n. If the heap has reached size k, return the root; else return −1 (fewer than k elements exist yet).

⚠ PITFALL — handle the "not enough elements yet" case. Before k values have arrived there is no valid k-th largest; return −1 (or a sentinel) rather than peeking an under-filled heap.

class MinHeap {
    final PriorityQueue<Integer> pq;
    final int k;

    public MinHeap(int k) {
        this.k = k;
        pq = new PriorityQueue<>(k);   // min-heap
    }

    public int add(int n) {
        if (pq.size() < k) {           // still filling the heap
            pq.add(n);
        } else if (pq.peek() < n) {    // n beats the smallest of top-k
            pq.poll();
            pq.add(n);
        }
        if (pq.size() == k) return pq.peek();   // current k-th largest
        else return -1;                         // fewer than k seen
    }
}

Time O(log k) per add · Space O(k) — you store only k elements regardless of how long the stream runs.

Streaming/online problems reward bounded state. The takeaway — maintain a fixed-size heap as persistent state — transfers to running medians (two heaps), sliding-window top-K, and any "answer a query after each update" design question.

Given M already-sorted lists of varying length, merge them into one fully sorted sequence, efficiently. Example: 4 lists → single sorted list of all elements.

Practice: LeetCode 23 — Merge k Sorted Listsleetcode.com/problems/merge-k-sorted-lists↗ (linked-list variant; same heap technique).

Brute force: concatenate all N elements and sort → O(N log N), throwing away the fact that each list is already sorted.

⭐ TRICK — a size-M min-heap seeded with only the FIRST element of each list. Because lists are pre-sorted, the global minimum must be one of the M list-heads. Poll the min, output it, then push the next element from the same list. The heap never exceeds M, so total cost is O(N log M) — better than O(N log N) since M ≤ N.

⚠ PITFALL — a bare value in the heap isn't enough; store a 3-field node. When you poll the minimum you must know which list it came from and which index within that list, to fetch the successor. Each heap entry needs {value, listNumber, index}. Forgetting the list-id/index is the classic bug here.

class Node implements Comparable<Node> {
    int value;   // the element
    int i;       // which list it came from
    int index;   // its position within that list
    Node(int value, int i, int index) { this.value = value; this.i = i; this.index = index; }
    public int compareTo(Node o) { return this.value - o.value; }   // min-heap by value
}

public static void printSorted(List<List<Integer>> lists) {
    PriorityQueue<Node> pq = new PriorityQueue<>();

    // seed: first element of every non-empty list
    for (int i = 0; i < lists.size(); i++) if (lists.get(i).size() >= 1) pq.add(new Node(lists.get(i).get(0), i, 0));

    while (!pq.isEmpty()) {
        Node min = pq.poll();
        System.out.print(min.value + " ");          // emit the smallest

        int nextIdx = min.index + 1;                 // successor in the SAME list
        if (nextIdx < lists.get(min.i).size()) {
            min.index = nextIdx;
            min.value = lists.get(min.i).get(nextIdx);
            pq.add(min);                             // push successor back
        }
    }
}

Time O(N log M) · Space O(M), where N = total elements, M = number of lists. The heap holds at most one live entry per list.

💡 TIP — "already sorted" is a signal to exploit, not re-sort. Dumping everything into one array and sorting ignores the given structure. The heap's root-is-minimum property lets you produce output in order with only M candidates in play at any time — the reusable idea behind external merge sort and merging sorted files too large for memory.

Given a binary tree, decide whether it is a min-heap — i.e. (a) a complete binary tree, and (b) every node's value ≤ both of its children's values.

Practice: GeeksforGeeks — "Check if a given binary tree is heap"geeksforgeeks.org/check-if-a-given-binary-tree-is-heap↗. [+] Not a standard LeetCode problem.

⭐ TRICK — check completeness and ordering in ONE DFS using array-indexing. Imagine the tree stored in an array: the root is index 0, and a node at index i has children at 2i+1 and 2i+2. Recurse with three parameters — (node, i, n) where n = total node count. If any node's index i ≥ n, the tree has a "gap" → not complete → not a heap. This folds the completeness check into the same traversal as the value check.

⚠ PITFALL — null-check children before comparing values. Comparing node.data against a null child throws a NullPointerException. Guard each child with != null first.

💡 TIP — know what your recursive booleans mean. left = "is the left subtree of the current node a valid min-heap?"; same for right. The return is left && right after the current node passes its own checks. Being able to state the meaning of each recursive result is what lets you adapt this to any new tree problem on the spot.

// count total nodes
private static int size(Node root) {
    if (root == null) return 0;
    return 1 + size(root.left) + size(root.right);
}

private static boolean isHeap(Node root, int i, int n) {
    if (root == null) return true;    // empty subtree is a valid heap
    if (i >= n) return false;         // index out of range → not complete

    // min-heap violation: a child smaller than the parent
    if ((root.left  != null && root.left.data  <= root.data) ||(root.right != null && root.right.data <= root.data)) return false;

    boolean left  = isHeap(root.left,  2*i + 1, n);
    boolean right = isHeap(root.right, 2*i + 2, n);
    return left && right;
}

public static boolean isHeap(Node root) {
    return isHeap(root, 0, size(root));
}

Time O(n) · Space O(h) where h = tree height (recursion stack). [!] One definition writes the violation as child <= parent (strict min-heap disallowing equal children); another describes parent <= child (allowing equals). Use whichever definition the problem gives — the code above follows the strict form. Note: order the two recursive calls left-then-right (2i+1 before 2i+2) as shown.

The array-index-during-DFS trick generalizes. Encoding a tree's positional structure as indices lets you verify completeness, serialize/deserialize, or map a tree to a flat array in one pass — reusable for segment trees, binary-heap arrays, and complete-tree validation problems.

The meta-pattern: reach for a heap whenever you repeatedly need the current min or max of a changing set — top-K, greedy-merge, streaming queries, and k-way merges all reduce to "root gives me the extreme in O(1), maintenance is O(log size)."