Heaps & Greedy

Interview question: “From 50 million posts, return the 10 most trending hashtags.” If your first move is “sort everything,” you just sorted 50 million things to keep 10 — and the interviewer noted it. The heap is the data structure built for exactly this: it never sorts everything, it just always knows what’s best right now.

The Goal

By the end of this module you can:

• Explain the heap promise — best element in O(1), insert and remove in O(log n) — and what it deliberately does NOT promise
• Implement a min-heap on a plain int[] array using the index formulas, no node objects
• Use Java’s PriorityQueue correctly, including a max-heap comparator that doesn’t silently overflow
• Solve top-K problems with a size-K heap in O(n log k), and explain why it’s a MIN heap for top-K LARGEST
• Recognize when greedy is provably correct (meeting rooms) and when it silently lies to you (coin change)

The Lesson

The heap promise — and the fine print

A heap is a container that makes exactly one promise: the best element is always on top. “Best” means smallest in a min-heap, largest in a max-heap. That’s the entire contract:

Read the fine print: a heap is not sorted. Element number 2 is one of the top’s children, but element number 7 could be anywhere in the bottom half. If you iterate a heap front to back, you get near-random order. The heap only guarantees the top — and that one guarantee, kept cheap, is worth everything.

The internal rule that makes it work: a heap is a complete binary tree where every parent is better than both its children. Insert at the bottom and bubble up — swap with the parent while you beat it. Remove the top by moving the last element up and sinking it down — swap with the better child while a child beats you. The tree stays balanced because it’s complete, so both walks are at most the tree’s height: O(log n).

The array trick — a tree with no nodes

Here’s the part that surprises people: production heaps don’t use node objects with left/right references. Because the tree is complete (filled left to right, no gaps), you can lay it flat in a plain array and compute family relationships with arithmetic. For 0-based index i:

flowchart TD
    A["index 0 value 3"] --> B["index 1 value 9"]
    A --> C["index 2 value 5"]
    B --> D["index 3 value 14"]
    B --> E["index 4 value 12"]
    C --> F["index 5 value 8"]

That tree IS the array [3, 9, 5, 14, 12, 8]. Same data, two views. Check it: parent of index 4 is (4-1)/2 = 1 — value 9, and 9 ≤ 12 holds. No new Node(...), no null checks, no pointer chasing — just index math on a contiguous array, which CPUs love. Remember the tree module (trees-bfs-dfs) where every node was an object? This is the exception that proves you should always ask “do I actually need node objects?”

Java’s PriorityQueue — and the overflow trap

Java ships a heap as java.util.PriorityQueue. It is a min-heap by default — poll() gives you the smallest:

import java.util.PriorityQueue;
import java.util.Comparator;

public class HeapDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.offer(50); minHeap.offer(10); minHeap.offer(30);
        System.out.println(minHeap.poll());  // 10 - smallest first

        // Max-heap: pass a comparator that reverses the order
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.offer(50); maxHeap.offer(10); maxHeap.offer(30);
        System.out.println(maxHeap.poll());  // 50 - largest first
    }
}

Now the classic trap. All over the internet you’ll see this max-heap:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);  // DON'T

b - a overflows. If b = -2_000_000_000 and a = 2_000_000_000, the true answer is about -4 billion — which doesn’t fit in an int, wraps around to a positive number, and your heap quietly orders things wrong. No exception, just wrong answers on large inputs. Write (a, b) -> Integer.compare(b, a) or Comparator.reverseOrder(). Always.

One more PriorityQueue gotcha: remove(someObject) is O(n) — it has to search the array. The heap is fast at the top and slow everywhere else. If a problem needs arbitrary removals, a heap alone is the wrong tool.

The size-K trick — the template you’ll use most

The signal “top K largest out of n” has a brute-force answer: sort everything, take the last K. That’s O(n log n). The heap answer is O(n log k) — and when n is 50 million and k is 10, log k is tiny and the win is massive.

import java.util.PriorityQueue;

public class TopK {
    // Returns the k largest values from nums
    static int[] topKLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();  // MIN-heap. Yes, min.
        for (int n : nums) {
            heap.offer(n);
            if (heap.size() > k) heap.poll();  // evict the weakest of the current top K
        }
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) result[i] = heap.poll();
        return result;
    }

    public static void main(String[] args) {
        int[] spends = {1200, 50, 9800, 430, 7600, 310, 8800};
        for (int v : topKLargest(spends, 3)) System.out.println(v);  // 9800 8800 7600
    }
}

Stop and absorb the counterintuitive part: to find the LARGEST elements, you use a MIN heap. Why? Because the heap is your VIP room of size K, and the only question you ever ask is “who is the weakest person currently inside?” — because that’s who a newcomer must beat to get in. A min-heap answers exactly that question in O(1) at the top. The smallest of the top K is the bouncer at the door. A max-heap of all n elements would also work, but that’s O(n) memory and you’re back to nearly sorting everything.

For a billion events streaming past with k = 100, the size-K heap doesn’t even need the data to fit in memory. That’s why this is the streaming-analytics workhorse.

Greedy — heaps’ partner in crime

Greedy lives in this module because a heap is how greedy gets implemented: greedy means “repeatedly take the best available option,” and a heap is the machine that serves up the best available option in O(log n).

Greedy means: take the locally best move, commit, never look back. No undo, no exploring alternatives. When it works, it’s the simplest and fastest answer in the room. The classic provably-correct case is activity selection — attend the maximum number of non-overlapping meetings:

import java.util.Arrays;
import java.util.Comparator;

public class Meetings {
    static int maxMeetings(int[][] meetings) {            // each meeting is {start, end}
        Arrays.sort(meetings, Comparator.comparingInt(m -> m[1]));  // earliest END first
        int count = 0;
        int freeAt = Integer.MIN_VALUE;
        for (int[] m : meetings) {
            if (m[0] >= freeAt) {   // it starts after I'm free - take it, never reconsider
                count++;
                freeAt = m[1];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] day = {{9, 10}, {9, 12}, {10, 11}, {11, 13}};
        System.out.println(maxMeetings(day));  // 3
    }
}

Why is “earliest end first” provably right? Because finishing earliest leaves the most room for everything after — any meeting an alternative choice could fit, the earliest-ending choice can fit too. The greedy choice is never worse than any other. That’s what a greedy proof looks like: show the local choice can always be swapped into an optimal answer without making it worse.

Now watch greedy fail. Coin change: make 6 rupees with coin types {1, 3, 4}, fewest coins. Greedy says “take the biggest coin that fits, repeat”:

Greedy: three coins (4+1+1). The actual best: two coins (3+3). Greedy committed to the 4 and never looked back — but the 4 was a trap. No error, no warning, just a confidently wrong answer. (With real denominations like {1, 2, 5, 10} greedy happens to work, which is exactly why it feels trustworthy and isn’t.)

When the locally best move can sabotage the global answer, you need a technique that explores alternatives and remembers results. That technique is dynamic programming, and this failing example is the front door of dp-intro.

See It Move

Watch how an insert bubbles up and an extract-min sinks down — and keep one eye on the array panel, because the tree and the array are the same object.

Step through it and notice:

• An inserted element lands at the end of the array (bottom of the tree) and swaps upward only while it beats its parent — usually just 2–3 swaps, never the whole structure.
• Extract-min takes the root, moves the last array element into slot 0, then sinks it down toward the better child.
• After every operation, check the array: parents at (i-1)/2 always beat children at 2i+1 and 2i+2 — but the array as a whole is never sorted.
• Count the swaps per operation and compare with the number of tree levels. That’s your O(log n), visible.

Spot The Pattern

Where It Runs In Real Life

OS task schedulers. Your operating system has thousands of runnable threads and one question every few milliseconds: “who runs next?” Priority-based schedulers keep runnable tasks in heap-like priority queues so the most urgent task surfaces in O(log n), not via rescanning every task.

Dijkstra in map routing. Every “fastest route” you’ve asked a maps app for runs a shortest-path search that repeatedly asks “which unexplored point is currently cheapest to reach?” That’s a min-heap polled millions of times per query. Without it, Dijkstra degrades from O(E log V) to O(V²) and your route takes seconds instead of milliseconds.

Top-K dashboards. Trending hashtags, “top 10 spenders this month” on a fintech dashboard, most-played songs — these are all size-K min-heaps sitting on event streams. The stream never fits in memory; the K-slot heap doesn’t care.

Hospital triage. Emergency rooms are literally a priority queue: patients are processed by severity, not arrival order, and a new critical case bubbles straight past the queue. Hospital management systems implement exactly the structure you’re building below.

Database external sort — the merge phase. When a database sorts a table bigger than RAM, it sorts chunks to disk, then merges hundreds of sorted runs back together. The merge keeps one head element per run in a min-heap — the merge-K-sorted pattern, running inside every serious database engine.

Build This

You’re building a hospital triage heap from scratch — a min-heap on a plain int[] where a lower number means a more critical patient. No PriorityQueue allowed until the extend step.

1. Create TriageHeap.java and type this — every line, no pasting:

public class TriageHeap {
    private int[] a = new int[16];
    private int size = 0;

    void insert(int severity) {
        if (size == a.length) a = java.util.Arrays.copyOf(a, size * 2);
        a[size] = severity;
        bubbleUp(size);
        size++;
    }

    int extractMin() {
        int min = a[0];
        size--;
        a[0] = a[size];      // last element jumps to the root
        sinkDown(0);
        return min;
    }

    private void bubbleUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (a[i] >= a[parent]) break;   // parent is better - stop
            swap(i, parent);
            i = parent;
        }
    }

    private void sinkDown(int i) {
        while (true) {
            int left = 2 * i + 1, right = 2 * i + 2, best = i;
            if (left < size && a[left] < a[best]) best = left;
            if (right < size && a[right] < a[best]) best = right;
            if (best == i) break;           // beats both children - stop
            swap(i, best);
            i = best;
        }
    }

    private void swap(int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

    public static void main(String[] args) {
        TriageHeap er = new TriageHeap();
        int[] arrivals = {7, 2, 9, 1, 5, 3, 8};   // severity per arriving patient
        for (int s : arrivals) er.insert(s);
        System.out.print("Treatment order: ");
        while (er.size > 0) System.out.print(er.extractMin() + " ");
        System.out.println();
    }
}

2. Compile and run. You must see Treatment order: 1 2 3 5 7 8 9 — patients out by severity even though they arrived in chaos.

3. Add one debug line at the top of extractMin: print java.util.Arrays.toString(java.util.Arrays.copyOf(a, size)). Run again and confirm with your own eyes that the array is never fully sorted — only the front is guaranteed.

4. Break it. Comment out the swap(i, parent) line in bubbleUp (keep i = parent;). Recompile, run. The treatment order is now wrong with no exception thrown — the most dangerous kind of bug. A heap that doesn’t maintain its property doesn’t crash; it just lies. Fix it back.

5. Extend it — flip one comparison. Change a[i] >= a[parent] to a[i] <= a[parent] in bubbleUp and the two < to > in sinkDown. You now have a max-heap. Run it, confirm 9 8 7 ..., then flip everything back. The entire min/max difference is three comparison operators.

6. Extend it — the 5-line version. Below main, write a second method that does the same triage using java.util.PriorityQueue in about 5 lines. Same output. Now you know exactly what those 5 lines are hiding — and you’ll never be the candidate who can use PriorityQueue but can’t explain it.

Problems To Solve

For the full drill list, work through the Heap / Priority Queue and Greedy sections of neetcode.io’s roadmap.

The rule: solve until you can write the size-K template from memory. If you’re stuck 25 minutes, read the approach, close it, and re-solve from scratch.

Check Yourself

1. What three operations does a heap promise, at what cost — and what does it explicitly NOT promise?
2. For 0-based index i, give the formulas for parent, left child, and right child.
3. Why can a heap live in a plain array with no node objects, when a general binary tree can’t?
4. Java’s PriorityQueue — min-heap or max-heap by default? How do you safely get the other one?
5. Why is (a, b) -> b - a a landmine, and what do you write instead?
6. You need the top 100 largest values from a stream of a billion. Which heap, what size, and why that polarity?
7. Greedy works for “maximum meetings” but fails for coins {1, 3, 4}. What’s the structural difference?
8. You poll() a PriorityQueue of 7 elements once, then iterate the rest with a for-each loop. What order do you get?

Explain it out loud: Explain to an empty chair why finding the top 10 LARGEST spenders uses a MIN-heap of size 10 — use the bouncer-at-the-VIP-door picture, then explain what would go wrong (memory and time) with a max-heap of everything. If the min/max part still feels backwards, re-read the size-K section.

Still Unclear?

Copy-paste any of these into Claude — they deepen understanding without doing the work for you:

I am learning heaps in Java. Quiz me: give me 5 one-line problem descriptions,
and I will answer whether each needs a heap, greedy, sorting, or something else,
and which polarity (min or max) and what size. Tell me what I got wrong and why,
but never give the answer before my attempt.

Walk me through why the earliest-end-time greedy choice for the maximum meetings
problem is provably optimal, using an exchange argument in plain language. Then
show me a different interval problem where the same greedy instinct fails.
Do not write any code.

I built a min-heap on an int array. Ask me to predict the exact array contents
after each of these operations: insert 5, insert 2, insert 8, insert 1,
extract-min, extract-min. Check each prediction and correct my index math
if I drift.

Why AI Can’t Do This For You

AI will write you a flawless PriorityQueue snippet on request. What it can’t do is sit in your interview when the question says “design the trending-products widget” and nobody says the word heap — recognizing that “top K out of a stream” is hiding in that sentence, in 30 seconds, under pressure, is the skill. Same in production: the ticket says “the dashboard query is timing out,” not “replace this O(n log n) sort with an O(n log k) heap.”

Greedy is even less delegable. AI will happily write a greedy solution for coin change with arbitrary denominations — confidently, compilably, wrongly. Knowing when greedy is allowed to be trusted is a judgment call about proof, not syntax. The person who can smell “this local choice might sabotage the global answer” is the person who catches that bug in code review. That instinct only comes from having watched greedy fail with your own eyes — which you just did.

Module done? Add it to today’s tracker