12 — Heaps / Priority Queues

What a heap is

A binary heap is a tree where every node is smaller than both its children (a min-heap) or larger than both (a max-heap).

min-heap:        1
                / \
               3   2
              / \
             5   4

Notice this is not sorted — 3 comes before 2 when read level by level. The only guarantee is parent ≤ children, which means the minimum is always at the root.

Why a weaker guarantee is the point

Full sorting costs O(n log n) and gives you complete order. But if you only ever need the minimum, that's more than you're paying for.

The heap property is cheap to maintain:

• Insert: put the new element at the bottom, then swap it upward while it's smaller than its parent. At most log n swaps (the tree's height).
• Remove the min: take the root, move the last element to the top, then swap it downward. Again at most log n.

The characteristic saving: finding the top k of n items by sorting is O(n log n). With a size-k heap it's O(n log k) time and O(k) space. When k is small — or when data streams in and re-sorting isn't possible — that's the whole answer.

Java configuration

PriorityQueue<Integer> minHeap = new PriorityQueue<>();                       // smallest first
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>((a, b) -> b - a);      // watch overflow

// Pairs — the common interview shape: {distance, id}, {cost, node}
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{dist, node});
int[] top = pq.poll();

// O(n) heapify from a collection — cheaper than n inserts at O(n log n)
PriorityQueue<Integer> h = new PriorityQueue<>(existingList);

Comparator.comparingInt is preferred over (a, b) -> a - b, which can overflow and silently sort wrongly (03).

Costs to have ready: offer/poll O(log n), peek O(1), contains/remove(Object) O(n), construction from a collection O(n). Iteration is not sorted.

Pattern 1 — bounded heap for top-k

The counter-intuitive part

To find the k LARGEST elements, use a MIN-heap.

Here's why. You keep a heap containing exactly the k best you've seen. When a new element arrives, you must decide whether it beats the weakest current member — so you want the weakest instantly accessible.

In a min-heap of the k largest, the root is the smallest of the large ones — precisely the one to evict.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
    minHeap.offer(n);
    if (minHeap.size() > k) minHeap.poll();   // over capacity — drop the weakest
}
return minHeap.peek();                        // the kth largest

Trace: nums = [3, 2, 1, 5, 6, 4], k = 2.

peek() = 5, the 2nd largest. ✓

Symmetrically: for the k smallest, use a max-heap of size k.

Kth Largest in a Stream

Same heap, kept alive as a field. This is where heaps genuinely beat sorting — you can't re-sort on every arrival.

private final PriorityQueue<Integer> minHeap = new PriorityQueue<>();
private final int k;

public KthLargest(int k, int[] nums) {
    this.k = k;
    for (int n : nums) add(n);
}

public int add(int val) {
    minHeap.offer(val);
    if (minHeap.size() > k) minHeap.poll();
    return minHeap.peek();
}

Alternatives worth naming

A heap isn't always optimal. State these to show you know the landscape:

Quickselect is the partition step of quicksort: pick a pivot, partition, and recurse only into the half containing the kth position. Since you discard half each time, the expected total is O(n).

The honest summary: heap for streams and small k; quickselect for a one-off offline query; bucket sort when values are bounded counts.

Pattern 2 — heap with a derived key

Sort by a computed metric without materializing it.

// K Closest Points to Origin
PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
    (a, b) -> (b[0]*b[0] + b[1]*b[1]) - (a[0]*a[0] + a[1]*a[1]));

for (int[] p : points) {
    maxHeap.offer(p);
    if (maxHeap.size() > k) maxHeap.poll();     // evict the FARTHEST
}

int[][] res = new int[k][2];
for (int i = 0; i < k; i++) res[i] = maxHeap.poll();
return res;

Skip the square root. Real distance is √(x² + y²), but squaring is monotonic on non-negative values — if d₁ < d₂ then d₁² < d₂². So comparing squared distances gives identical ordering while avoiding floating-point math and its precision issues.

That's a small, free point. Make it.

Note the polarity: k closest means we want the k smallest distances, so we use a max-heap and evict the largest. Same inversion as before.

Pattern 3 — repeated extract-and-reinsert (simulation)

When the process itself says "take the largest, do something, put the result back":

// Last Stone Weight: smash the two heaviest; if unequal, the difference goes back
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int s : stones) maxHeap.offer(s);

while (maxHeap.size() > 1) {
    int a = maxHeap.poll(), b = maxHeap.poll();   // two heaviest
    if (a != b) maxHeap.offer(a - b);             // remainder goes back in
}
return maxHeap.isEmpty() ? 0 : maxHeap.peek();

Trace: [2, 7, 4, 1, 8, 1].

The isEmpty() guard matters: all stones can cancel out (e.g. [2, 2]), leaving nothing.

Pattern 4 — k-way merge

Merge k sorted sequences. Hold one element from each source; poll the smallest, then pull the next from that same source.

PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
for (ListNode l : lists) if (l != null) pq.offer(l);

while (!pq.isEmpty()) {
    ListNode node = pq.poll();
    tail.next = node;
    tail = node;
    if (node.next != null) pq.offer(node.next);   // refill from the SAME list
}

The heap never exceeds k entries — one per list. That's the whole point, and why this is O(N log k) rather than O(N log N).

Why it's correct: the smallest unconsumed element across all lists must be at the head of one of them (each list is sorted). The heap holds exactly those heads, so its minimum is the global minimum.

See 11 — Linked List for the full Merge K Sorted Lists solution.

Design Twitter

getNewsFeed merges the 10 most recent tweets across everyone a user follows. Classic k-way merge, capped at 10 so you never merge more than you need.

// each user's tweets stored newest-LAST as {timestamp, tweetId}
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);

for (int followee : following.getOrDefault(userId, Set.of())) {
    List<int[]> feed = tweets.get(followee);
    if (feed != null && !feed.isEmpty()) {
        int last = feed.size() - 1;
        int[] t = feed.get(last);
        // carry the owner and index so we can walk BACKWARDS through their feed
        maxHeap.offer(new int[]{t[0], t[1], followee, last});
    }
}

List<Integer> res = new ArrayList<>();
while (!maxHeap.isEmpty() && res.size() < 10) {
    int[] top = maxHeap.poll();
    res.add(top[1]);
    int idx = top[3] - 1;
    if (idx >= 0) {
        int[] prev = tweets.get(top[2]).get(idx);
        maxHeap.offer(new int[]{prev[0], prev[1], top[2], idx});
    }
}
return res;

Spec detail interviewers check: a user must see their own tweets. Either have them follow themselves at registration, or explicitly include userId in the loop. Missing it is the standard bug.

Pattern 5 — two heaps for a running median

The signature design problem: support addNum and findMedian on a growing stream.

The idea

The median is the middle of sorted data. Keeping everything sorted costs O(n) per insert. But you don't need full order — you only need the middle.

So split the data in half:

• A max-heap holding the lower half — its root is the largest of the small values.
• A min-heap holding the upper half — its root is the smallest of the large values.

        lower (max-heap)        upper (min-heap)
        [1, 2, 3]               [4, 5, 6]
              ↑ root                ↑ root
              └──── the median is here ────┘

The two roots sit right at the boundary. If the halves are equal in size, the median is their average. If lower has one extra, the median is its root.

The implementation

private final PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
private final PriorityQueue<Integer> upper = new PriorityQueue<>();                            // min-heap

public void addNum(int num) {
    lower.offer(num);                    // 1. always push to lower
    upper.offer(lower.poll());           // 2. move its largest across
    if (upper.size() > lower.size()) {   // 3. rebalance if upper got too big
        lower.offer(upper.poll());
    }
}

public double findMedian() {
    if (lower.size() > upper.size()) return lower.peek();
    return (lower.peek() + upper.peek()) / 2.0;
}

Why the three-step add works unconditionally

Step 1 puts the new number in lower regardless of its value — possibly violating "everything in lower ≤ everything in upper".

Step 2 immediately moves lower's largest into upper. Whatever the new number was, after this move lower's maximum is ≤ upper's minimum. The invariant is restored without a single comparison.

Step 3 fixes only the sizes, keeping lower equal to or one larger than upper.

That's why it's memorizable verbatim — the push-then-transfer trick means you never write an if about where the number belongs.

Trace — adding 1, 2, 3:

✓ addNum is O(log n), findMedian is O(1).

Follow-ups to have ready

• "All values are 0–100." → A counting array: O(1) add, O(100) = O(1) median.
• "99% of values are in a small range." → Counting array for the common range, plus two overflow lists for the outliers.

Pattern 6 — greedy scheduling (Task Scheduler)

Identical tasks need n cooldown units between them. Find the minimum total time.

The greedy rule: always run the task with the most remaining occurrences that is currently off cooldown. The most frequent task is the bottleneck, so keep it moving.

Two structures: a max-heap for "most remaining", and a queue for "on cooldown".

int[] counts = new int[26];
for (char c : tasks) counts[c - 'A']++;

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int c : counts) if (c > 0) maxHeap.offer(c);

Deque<int[]> cooldown = new ArrayDeque<>();   // {remainingCount, timeItBecomesAvailable}
int time = 0;

while (!maxHeap.isEmpty() || !cooldown.isEmpty()) {
    time++;
    if (!maxHeap.isEmpty()) {
        int remaining = maxHeap.poll() - 1;
        if (remaining > 0) cooldown.offer(new int[]{remaining, time + n});
    }
    if (!cooldown.isEmpty() && cooldown.peek()[1] == time) {
        maxHeap.offer(cooldown.poll()[0]);        // cooldown expired — available again
    }
}
return time;

If the heap is empty but the cooldown queue isn't, the CPU idles — time++ still runs, which is exactly right.

The O(1) math answer

int maxCount = Arrays.stream(counts).max().orElse(0);
int numMax = (int) Arrays.stream(counts).filter(c -> c == maxCount).count();
return Math.max(tasks.length, (maxCount - 1) * (n + 1) + numMax);

Deriving it: picture the most frequent task laid out in frames of width n + 1:

A _ _ | A _ _ | A _ _ | A
\_____/ \_____/ \_____/
 maxCount - 1 full frames     then the final A

That's (maxCount - 1) × (n + 1) slots, plus a final round holding every task tied for the maximum — hence + numMax.

Math.max(tasks.length, ...) covers the case where there are so many distinct tasks that the gaps fill naturally and no idling ever happens. Then the answer is simply the number of tasks.

Give the heap simulation first — it demonstrates the mechanism and is easier to justify. Then offer the formula as the optimization.

When not to use a heap

• You need arbitrary removal. remove(Object) is O(n). Use lazy deletion or a TreeMap.
• You need ordered iteration or neighbour queries. That's TreeMap/TreeSet.
• You need the whole thing sorted once. Just sort — n polls cost the same O(n log n) with more code.
• The key is a bounded count. Bucket by count in O(n).

Lazy deletion — the standard workaround

Rather than paying O(n) to remove a stale entry from the middle of the heap, leave it there and skip it when it surfaces:

while (!pq.isEmpty() && isStale(pq.peek())) pq.poll();   // discard outdated entries at read time

This appears in Dijkstra (18) and in Minimum Interval to Include Each Query (21). It's worth recognizing as a named technique — "I'll use lazy deletion" is a sentence that lands well.

Recognition checklist

Complexity summary