24

Heaps & Priority Queues

Always know the smallest (or largest) thing — and update it in O(log n).

intermediate~85 min8 simulations14 problems

▶ guided lesson⚡ 1-minute summary↻ 14 recall cards

before this: Tree Recursion · Arrays & Strings · Sorting

01 · why it exists

Why this exists, and the weight it carries

since1964

Binary heap: sift up and sift down

J. W. J. Williams

The binary heap arrived in June 1964, inside J. W. J. Williams's Algorithm 232: Heapsort in Communications of the ACM. It keeps a tree in a plain array with a single rule — every parent ≤ its children — so the minimum is always the first element (A[1] in his ALGOL, index 0 in Java). The Java Toolkit chapter's PriorityQueue card tells how this structure became java.util.PriorityQueue in Java 5. This card is about the two moves that make it work: sift up and sift down.

the problem it solvedTaking the smallest item again and again while new items keep arriving — O(log n) per step instead of re-sorting everything.

its jobs today

  • java.util.PriorityQueue is exactly this array heap: its source comment says the two children of queue[n] are queue[2*n+1] and queue[2*(n+1)].
  • Java's ScheduledThreadPoolExecutor keeps delayed tasks in a heap-based queue, so the next task due always sits on top.
  • Dijkstra's shortest paths (the Shortest Paths chapter) pulls the closest unsettled place from a min-heap at every step.

the weight it carries

Illustrative: a delivery app keeps 10 lakh (1,000,000) pending orders by promised time. The heap has ⌊log₂ 1,000,000⌋ + 1 = 20 levels, so an offer or poll does at most 19 swaps (a poll compares about 2 × 19 = 38 times). Re-sorting after every new order would cost about 1,000,000 × 20 = 2 crore comparisons each time.

without it

"Give me the next most urgent item" would mean a full scan or a re-sort on every call — O(n) or O(n log n) instead of O(log n).

when · why · how

when
You repeatedly need the current min (or max) while items are added and removed.
why
offer and poll walk one path of height ⌊log₂ n⌋ → O(log n); peek is O(1). The price: there's no full order, so contains and remove(x) are O(n).
how
PriorityQueue<Integer> pq = new PriorityQueue<>(); (min-heap) or new PriorityQueue<>(Comparator.reverseOrder()) (max-heap); then offer, poll, peek.

02 · plain english

The idea in 30 seconds

A heap is a complete binary tree where every parent is ≤ its children (min-heap). So the minimum is always on top.

It isn't fully sorted — only parent vs child is ordered. That weaker promise is what makes insert and remove-min cheap: O(log n).

It lives in a plain array: the children of index i are 2i+1 and 2i+2, the parent is (i−1)/2. Java's PriorityQueue is exactly this.

picture this

Think of the scheduler behind Task Manager: dozens of processes are waiting, and the CPU always picks the most urgent one next. When a new process arrives, it is slotted in with a few comparisons — nobody re-sorts the whole waiting list.

03 · remember

What you must know

  • Heap property: min-heap → every parent ≤ its children (max-heap: ≥). Siblings have no order, so the array is not sorted.
  • Shape property: the tree is complete — every level full except the last, which fills left to right. That's why it fits in an array with no gaps and has height ⌊log₂ n⌋.
  • Index math (0-based): parent(i) = (i − 1) / 2, left(i) = 2i + 1, right(i) = 2i + 2.
  • offer = append + sift up: swap with the parent while smaller. poll = take root, move the last leaf to the root, sift down: swap with the smaller child while bigger. Both walk one path: O(log n). peek is O(1).
  • Build a heap in O(n) (heapify): sift down every parent from the last one up to the root. Most nodes are near the bottom and barely move, so the total work is linear — not n log n.
  • `PriorityQueue` is a min-heap by default. Max-heap: new PriorityQueue<>(Comparator.reverseOrder()). remove(Object) and contains are O(n) — a heap can't find an arbitrary element fast.
  • Top-k pattern: k largest → keep a min-heap of size k (the root is the weakest of the winners and gets kicked out). k smallest → max-heap of size k. O(n log k).
  • Two heaps (max-heap for the lower half, min-heap for the upper half) give a running median; k-way merge keeps one cursor per sorted list in a heap — also for "rows" you never build, like the sum table in Find K Pairs.
  • Greedy with a heap: keep the candidates in a heap and act on the best one now (heaviest stone, biggest affordable profit). When candidates unlock over time, sort them by the unlock key once and push them in as they unlock.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

offer — append and sift up

Tree and array are the same data. Watch a value bubble up while it's smaller than its parent at (i−1)/2.

loading simulation…
sim

poll — take the root, sift down

The last leaf jumps to the root to keep the tree complete, then sinks past the smaller child.

loading simulation…
sim

Heapify in O(n)

Leaves are already heaps (green). Fix each parent from the bottom up — count the swaps against n.

loading simulation…
sim

Heap sort in place

One array: a shrinking max-heap on the left, a growing sorted block on the right.

loading simulation…
sim

Top-k with a size-k min-heap

The root is the bouncer: anything smaller than it never gets into the top k.

loading simulation…
sim

Running median with two heaps

A max-heap holds the smaller half, a min-heap the larger half. The middle values always sit on the two tops.

loading simulation…
sim

K-way merge — one candidate per list

The heap never holds more than one node per list. Poll the smallest, append it, offer that list's next node.

loading simulation…
sim

Greedy with a heap — IPO

Projects unlock as capital grows (sorted by capital); the max-heap always hands over the biggest profit you can afford.

loading simulation…

05 · cost

Time & space, explained

Binary heap / PriorityQueue (n elements)
TimeWhy it's that fast (or slow)why
peek (min)O(1)Read index 0The heap property puts the minimum at the root.
offer / addO(log n)Sift up ≤ heightThe new value climbs at most ⌊log₂ n⌋ levels (amortized: the array occasionally grows).
poll / remove()O(log n)Sift down ≤ heightThe moved leaf sinks at most ⌊log₂ n⌋ levels.
Build from n values (heapify / new PriorityQueue<>(collection))O(n)Σ heights ≤ nn/2 leaves do no work, n/4 nodes sink ≤ 1 level, n/8 sink ≤ 2… the series sums to less than n.
n separate offersO(n log n)Each is O(log n)Building one-by-one is slower than heapify (still fine in practice).
remove(Object) / containsO(n)Linear scanSiblings aren't ordered, so finding an arbitrary value means checking everything.
Heap sortO(n log n)In place, O(1) extraHeapify O(n) + n polls of O(log n). Worst case too — but not stable.
Iterate / toStringO(n)Array order, NOT sortedOnly polling repeatedly gives sorted order.
Finding the k largest of n
TimeExtra spacewhy
Sort everythingO(n log n)O(log n) – O(n)Simple, but does far more work than needed when k is small.
Size-k min-heapO(n log k)O(k)Each element costs O(log k); works on streams that never end.
Heapify all, then poll k timesO(n + k log n)O(n)Linear build, then k cheap pops.
Quickselect (random pivot)O(n) average, O(n²) worstO(1) in placePartition and keep only the side with the answer: n + n/2 + n/4 + … ≈ 2n.
Counting / buckets (bounded values)O(n + range)O(range)No comparisons at all when values or frequencies are small integers.
Heap patterns at a glance
TimeExtra spacewhy
Two heaps: addNum / findMedianO(log n) / O(1)O(n)At most five heap operations per add; the median is read from the two tops.
K-way merge of N items from k sorted listsO(N log k)O(k)Every item enters and leaves a heap that holds one cursor per list.
K smallest pair sums (Find K Pairs)O(k log min(n₁, k))O(min(n₁, k))k polls on a heap of row cursors — the n₁·n₂ sum table is never built.
Sort + heap greedy (IPO)O(n log n + k log n)O(n)One sort to unlock in order; each project enters and leaves the heap at most once.

06 · java

Raw vs Collections Framework

A heap by hand vs PriorityQueue

javaarray-backed MinHeapjava.util.*
/** A binary min-heap of ints stored in an array: children of i are 2i+1 and 2i+2, parent is (i-1)/2. */class MinHeap {    private int[] a = new int[16];    private int size = 0;     void offer(int x) {        if (size == a.length) a = Arrays.copyOf(a, size * 2);   // grow like ArrayList        a[size] = x;                                   // new value goes in the next free slot        siftUp(size++);    }     private void siftUp(int i) {        while (i > 0) {            int parent = (i - 1) / 2;            if (a[parent] <= a[i]) break;              // order holds: stop            swap(i, parent);                           // smaller value bubbles up            i = parent;        }    }     int peek() {        if (size == 0) throw new NoSuchElementException();        return a[0];                                   // the minimum is always the root    }     int poll() {        if (size == 0) throw new NoSuchElementException();        int top = a[0];        a[0] = a[--size];                              // last leaf jumps to the root        siftDown(0);        return top;    }     private void siftDown(int i) {        while (true) {            int left = 2 * i + 1, right = left + 1, smallest = i;            if (left < size && a[left] < a[smallest]) smallest = left;            if (right < size && a[right] < a[smallest]) smallest = right;            if (smallest == i) return;                 // both children are bigger: stop            swap(i, smallest);                         // larger value sinks            i = smallest;        }    }     /** Floyd's build-heap: sift down every parent, last parent first. O(n), not O(n log n). */    static MinHeap heapify(int[] values) {        MinHeap h = new MinHeap();        h.a = Arrays.copyOf(values, Math.max(16, values.length));        h.size = values.length;        for (int i = h.size / 2 - 1; i >= 0; i--) h.siftDown(i);   // leaves are already heaps        return h;    }     int size() {        return size;    }     private void swap(int i, int j) {        int t = a[i];        a[i] = a[j];        a[j] = t;    }}
  • PriorityQueue is a binary min-heap in an Object[] — the same sift-up/sift-down you see on the left.
  • Max-heap: new PriorityQueue<>(Comparator.reverseOrder()) or (a, b) -> Integer.compare(b, a). Never (a, b) -> b - a: it overflows for large values and silently mis-orders.
  • Order objects by a key with Comparator.comparingInt(...), add tie-breakers with .thenComparing(...).
  • Don't change an object's priority while it sits in the queue — the heap won't notice. Remove and re-add it, or push a new entry and skip stale ones when polled ("lazy deletion").
  • poll()/peek() return null on an empty queue; remove()/element() throw. PriorityQueue rejects null elements and isn't thread-safe (use PriorityBlockingQueue).

Heap sort

javain-place heap sortjava.util.*
class HeapSort {    /** In-place, O(n log n) worst case, O(1) extra space, not stable. */    static void sort(int[] a) {        int n = a.length;        for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, i, n);      // build a MAX-heap        for (int end = n - 1; end > 0; end--) {            swap(a, 0, end);                                          // max goes to its final slot            siftDown(a, 0, end);                                      // repair the shrunken heap        }    }     private static void siftDown(int[] a, int i, int n) {        while (true) {            int largest = i, left = 2 * i + 1, right = left + 1;            if (left < n && a[left] > a[largest]) largest = left;            if (right < n && a[right] > a[largest]) largest = right;            if (largest == i) return;            swap(a, i, largest);            i = largest;        }    }     private static void swap(int[] a, int i, int j) {        int t = a[i];        a[i] = a[j];        a[j] = t;    }}
  • Ascending order uses a max-heap: the largest goes to the end, then the heap shrinks by one.
  • Guaranteed O(n log n) with O(1) extra space — but not stable and cache-unfriendly, so Arrays.sort (dual-pivot quicksort / TimSort) is faster in practice.

Which heap for top-k?

javak largest → min-heap of size kjava.util.*
class Solution {    public int findKthLargest(int[] nums, int k) {        PriorityQueue<Integer> heap = new PriorityQueue<>();   // min-heap of the k largest so far        for (int x : nums) {            heap.offer(x);            if (heap.size() > k) heap.poll();                  // drop the smallest of k+1        }        return heap.peek();                                    // smallest of the top k    }}
  • It feels backwards: to keep the k largest, use a min-heap. Its root is the smallest of your winners — exactly the one to evict when something better arrives.
  • To keep the k smallest (closest points, cheapest items), use a max-heap of size k.
  • If you need all n elements in order anyway, a heap is overkill — sort.

Cursors in a heap: int[] entries and two-key comparators

javak-way merge over rows you never buildjava.util.*
class Solution {    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {        // a cursor {i, j} stands for the pair (nums1[i], nums2[j]); smallest sum on top.        // comparingInt, never (a, b) -> sumA - sumB: two sums can differ by 4·10⁹ and overflow        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(c -> nums1[c[0]] + nums2[c[1]]));        for (int i = 0; i < Math.min(nums1.length, k); i++) heap.offer(new int[] {i, 0});   // head of every row        List<List<Integer>> result = new ArrayList<>();        while (result.size() < k && !heap.isEmpty()) {            int[] c = heap.poll();                                   // smallest sum not taken yet            result.add(List.of(nums1[c[0]], nums2[c[1]]));            if (c[1] + 1 < nums2.length) heap.offer(new int[] {c[0], c[1] + 1});   // next pair in the same row        }        return result;    }}
  • A heap entry can be a small int[] cursor like {i, j} or {value, list, index} — the comparator decides what "smaller" means.
  • Comparator.comparingInt(c -> nums1[c[0]] + nums2[c[1]]) is overflow-safe as long as the key itself fits in an int. Subtracting two keys is not: two sums can differ by 4·10⁹.
  • Two keys: Comparator.comparingInt((String w) -> count.get(w)).thenComparing(Comparator.reverseOrder()) — count ascending, then word Z → A (the weakest word on top in Top K Frequent Words).
Java API you will actually use
calldoescost
new PriorityQueue<>()Empty min-heap (natural order)O(1)
new PriorityQueue<>(Comparator.reverseOrder())Max-heapO(1)
new PriorityQueue<>(Comparator.comparingInt(x -> key))Order objects/arrays by a keyO(1)
new PriorityQueue<>(collection)Heapify existing valuesO(n)
pq.offer(x) / pq.add(x)InsertO(log n)
pq.poll()Remove and return the min (null if empty)O(log n)
pq.peek()Look at the min (null if empty)O(1)
pq.size() / isEmpty()CountO(1)
pq.remove(x) / contains(x)Remove / find an arbitrary elementO(n)
pq.addAll(list)Offers one by oneO(m log n)

Repeatedly take the smallest/largest while adding new items

→ PriorityQueue

O(log n) offer/poll, O(1) peek.

k largest / k smallest of a big or endless stream

→ Size-k heap (opposite direction)

O(n log k) time, O(k) memory.

Running median

→ Two heaps (max-heap low half + min-heap high half)

O(log n) add, O(1) median.

Merge k sorted lists/arrays/streams

→ Min-heap of one cursor per source

O(N log k) — each element passes through a heap of size k.

Options that unlock over time (capital, time, fuel)

→ Sort by the unlock key + a max-heap of unlocked options

Each option is unlocked once and chosen at most once: O(n log n).

Remove arbitrary elements or find floor/ceiling

→ TreeMap / TreeSet

O(log n) for any key; a heap is O(n) for these.

Just the single min or max once

→ One linear scan

O(n), no heap needed.

07 · recognise

Spot the pattern

"k largest", "k smallest", "k closest", "top k frequent"

Size-k heap in the opposite direction (or quickselect / buckets)

"kth largest in a stream", values keep arriving

Size-k min-heap; the root is the answer

"median" of a changing collection

Two heaps, sizes balanced within one

Merge k sorted things

Min-heap of (value, source, index) cursors

"k smallest pairs / sums" from two sorted arrays

Each row of the sum table is sorted → k-way merge over rows

"smallest range" with one element from each of k lists

Heap of one pointer per list + track the max; always advance the min

Always process the most urgent / cheapest / biggest next (greedy)

Priority queue keyed by urgency (task scheduling, Dijkstra, stones)

Choices unlock as a resource grows ("at most k projects", capital, fuel)

Sort by the unlock threshold + max-heap of what's unlocked

"rearrange so no two equal items are adjacent"

Max-heap by count, hold back the last used item one turn

Schedule meetings / rooms by earliest end time

Min-heap of end times (see the Intervals chapter)

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

  • Expecting PriorityQueue to iterate or print in sorted order — only poll gives sorted order.
  • Comparator (a, b) -> a - b overflows (e.g. Integer.MIN_VALUE - 1). Use Integer.compare(a, b) or Comparator.comparingInt.
  • Putting all n values in a max-heap and polling k times for "k largest": correct, but O(n) memory and O(n log n) time when built by offers. A size-k min-heap needs O(n log k) time and O(k) memory.
  • Calling pq.remove(x) inside a loop — each call is O(n), so the loop becomes O(n²).
  • Mutating a field that the comparator reads while the object is inside the queue — the heap order silently breaks.
  • Integer overflow when averaging two medians: (a + b) / 2.0 with ints near 2³¹ — cast to long first.
  • Using int[] entries but comparing arrays with == — compare by the field you mean (a[0]).
  • Re-scanning every candidate each round in a greedy (IPO, task picking) — that's O(n·k). Sort once and let a heap hand you the best.

tricks

  • Say "heap" and "O(log n)" in the same breath, then say what's on top and why it's the right thing to have on top.
  • For any top-k problem, mention three options: sort (O(n log n)), heap (O(n log k)), quickselect (O(n) average). Pick the heap unless asked to optimize.
  • Draw the array and the tree side by side when explaining sift-up/down — interviewers love the index math.
  • Store int[] or a small record in the queue when you need value + source (k-way merge, Dijkstra).
  • When a problem says "stream" or "design", think about what must be fast: add, query, or both.
  • A heap makes a greedy fast, not correct. Say why the greedy choice is safe (an exchange argument) before you code it.

09 · why & how

Questions you might be too shy to ask

Why is a heap stored in an array instead of with TreeNode pointers?

Because it's always a complete tree: no gaps, so position i fully determines the parent and children by arithmetic. That saves the memory of two pointers per node and is very cache-friendly.

Why does building a heap take O(n), not O(n log n)?

Sift-down costs the node's height, not its depth. Half the nodes are leaves (height 0), a quarter have height 1, an eighth height 2… The sum n/4·1 + n/8·2 + n/16·3 + … is less than n. Sift-up-based building (n offers) is O(n log n) because the many bottom nodes may climb far.

How does a comparator decide what comes out first?

compare(a, b) returning a negative number means "a comes out before b". Integer.compare(a, b) → smaller first → min-heap (the default). Integer.compare(b, a) → for a = 5, b = 3 it returns negative, so 5 comes out first → max-heap. Simple hai: whatever your comparator calls "smaller" sits on top.

I printed my PriorityQueue and got [1, 2, 3, 5, 4]. Is it broken?

No. Printing (and a for-each loop) shows the heap's internal array, which is only parent ≤ child, not sorted. Offer 5, 1, 3, 2, 4 and that is exactly what Java prints — 5 and 4 are both children of 2, and siblings have no order. Only poll() gives sorted order: while (!pq.isEmpty()) out.add(pq.poll());.

Why does new PriorityQueue<int[]>() crash with ClassCastException?

Without a comparator, the queue assumes the elements are Comparable — like Integer or String. An int[] isn't, so the queue can't cast it to Comparable and throws — in modern Java (17+) already on the very first offer (old Java 8 waited until the second). Always pass the order you mean: new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])).

Heap vs sorted array vs BST — when do I use which?

Heap: you only ever need the min/max, with inserts mixed in (O(log n) each). Sorted array: mostly reads, rare inserts. BST/TreeMap: you need any key, floor/ceiling, or deletions of arbitrary elements in O(log n).

Why a MIN-heap for the k LARGEST elements?

You keep k winners and need to quickly find the weakest winner to compare against newcomers. The weakest of the largest values is the smallest — which a min-heap keeps on top.

Size-k heap: do I offer first and then poll, or check peek() first?

Both are correct. The simple way: pq.offer(x); if (pq.size() > k) pq.poll(); — the extra one always falls out. The slightly faster way: once the heap is full, offer only if x > pq.peek(), then poll. In an interview, write the simple version and mention the other. Same O(n log k).

Is PriorityQueue stable — do equal priorities come out in insertion order?

No. Ties come out in an unspecified order. If order matters, add a tie-breaker to the comparator (e.g. an increasing sequence number).

Median: why offer to low and then move its top to high? Isn't that wasted work?

It is a cheap way to keep the rule "every value in low ≤ every value in high" without an if. The new number goes into low; low's biggest value — maybe the new one — goes to high. So a big new number ends up in high; a small one stays in low, and low's old biggest moves up instead. The last step only fixes the sizes. Each step is O(log n), so it's still O(log n) per add.

How do I update the priority of something already in the queue?

Java's PriorityQueue has no decrease-key. Either remove(obj) (O(n)) and re-offer, or simply offer a new entry with the new priority and, when you poll an outdated one, skip it (lazy deletion). Dijkstra in Java usually does the latter.

How do I know a greedy-with-heap idea is actually correct?

The heap only makes the greedy fast. To trust it, use an exchange argument: take any best answer whose first choice differs from yours, swap your choice in, and show the result is no worse. If you can't, the problem may need DP instead — Last Stone Weight II (pick any two stones) is a DP, not a heap.

Should I write my own heap in an interview?

Usually no — use PriorityQueue and say "a binary min-heap, O(log n) offer and poll". Write one only when asked "implement a heap". Then you need just three things: the array, sift up and sift down. Knowing the index math (2i + 1, 2i + 2, (i - 1) / 2) is what they check.

What's the difference between a heap and "the heap" in Java memory?

Nothing in common but the name. The JVM heap is the memory area where objects live; the heap data structure is this priority tree.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.

  1. #703
    Kth Largest Element in a Streammust-do
    EasyAdobeAmazonMetaGoogleMicrosoft+1
  2. #1046
    Last Stone Weight
    EasyNVIDIAPayPalAmazonSalesforceBloomberg+1
  3. #215
    Kth Largest Element in an Arraymust-do
    MediumMetaAppleWalmartByteDance / TikTokAmazon+1
  4. #347
    Top K Frequent Elementsmust-do
    MediumMetaAppleOracleAmazonByteDance / TikTok+1
  5. #973
    K Closest Points to Originmust-do
    MediumMetaAmazonSalesforceAppleGoogle+1
  6. #621
    Task Scheduler
    MediumAmazonTCSOracleAppleMicrosoft+1
  7. #23
    Merge k Sorted Listsmust-do
    HardNVIDIAMetaOracleAmazonByteDance / TikTok+1
  8. #295
    Find Median from Data Streammust-do
    HardPayPalWalmartIntuitAmazonByteDance / TikTok+1
  9. #355
    Design Twitter
    MediumAdobeSalesforcePayPalAmazonGoogle+1
  10. #767
    Reorganize String
    MediumAmazonByteDance / TikTokOracleGoogleMicrosoft+1
  11. #373
    Find K Pairs with Smallest Sums
    MediumLinkedInAmazonGoogle
  12. #502
    IPO
    HardSamsungAmazonGoogle
  13. #632
    Smallest Range Covering Elements from K Lists
    HardAmazonGoogle
  14. #692
    Top K Frequent Words
    MediumUberBloombergAmazonGoogle

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

  1. #253
    Meeting Rooms II
    Mediumin IntervalsLeetCode Premium

    Sort meetings by start, keep a min-heap of end times: its size is the number of rooms in use.

  2. #743
    Network Delay Time
    Mediumin Shortest Paths

    Dijkstra is a greedy with a heap: always settle the closest unsettled node, skipping stale entries (lazy deletion).

  3. #912
    Sort an Array
    Mediumin Sorting

    Its heap-sort approach is this chapter's in-place heap: build a max-heap in O(n), then move the max to the end n times.

11 · revise

The whole chapter on one screen

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

  1. what it is

    A heap is a complete binary tree in an array: every parent ≤ its children (min-heap). The min sits at index 0; children of i are 2i + 1 and 2i + 2.

  2. cost

    peek O(1) · offer/poll O(log n) · build from n values O(n) · remove(x)/contains O(n) · heap sort O(n log n) in O(1) space.

  3. use it when

    You need the current min/max while items keep arriving: top-k, k closest, running median, merge k sorted lists, greedy "take the best next".

  4. template

    k largest: min-heap, pq.offer(x); if (pq.size() > k) pq.poll(); — the root is the k-th largest. k smallest: the same with a max-heap.

  5. template

    Median: max-heap low + min-heap high. Offer to low, move low's max to high, move it back if high is bigger. Median = the tops.

  6. template

    K-way merge: one cursor per sorted list in a min-heap. Poll the smallest, offer that list's next. O(N log k) time, O(k) space.

  7. trap

    Printing or iterating a PriorityQueue is NOT sorted — only repeated poll() returns values in order.

  8. trap

    (a, b) -> a - b overflows for far-apart values and silently mis-orders the heap. Use Integer.compare or Comparator.comparingInt.

  9. pro tip

    No decrease-key in Java: offer a new entry and skip stale ones when you poll them (lazy deletion), as Dijkstra does.

12 · recall

Flip, remember, repeat

card 1 / 14
recall

In a 0-indexed array heap, where are the parent and the children of index i?

tap or Space to flip ↻

Question 1: In a 0-indexed array heap, where are the parent and the children of index i?

13 · check yourself

Quick quiz

  1. In a 0-indexed array heap, where are the children of index 4?

  2. Which is a valid min-heap array?

  3. What is the time to build a heap from n unsorted values with bottom-up heapify?

  4. To find the 10 largest values in a stream of a billion numbers with little memory, you use…

  5. What does `System.out.println(pq)` print for a PriorityQueue after offering 5, 1, 8, 3?

  6. Why is `pq.remove(x)` O(n) for an arbitrary x?

  7. Two heaps for the running median: which heap holds the smaller half?

  8. Merging k = 100 sorted lists with 10⁶ nodes in total using a heap: at most how many entries are in the heap at once?

  9. In IPO, why sort the projects by required capital before using the max-heap?

0/0 correct · 9 left

14 · learn more

A second teacher, if you want one