Heap / Priority Queue

Reader guide and study workflow · Complete course map

You receive scores one at a time and must retain the best three. After scores [5,2,8], a new 6 arrives. Which value must be accessible to decide what stays? The smallest retained score, 2. Keeping the maximum readily available does not answer the replacement question.

Sorting all scores after every arrival would work. Keeping only three scores and sorting those repeatedly uses less memory, but still maintains more order than the decision needs. A min-heap exposes the weakest retained candidate while repairing only the path affected by insertion or removal.

Derive the retained set before the priority

For k=3, process [5,2,8,6,1,8]. The following rows display sorted retained multisets for readability, not the heap’s internal array:

Arrival	Candidates after insertion	Discard	Retained
5	[5]	none	[5]
2	[2,5]	none	[2,5]
8	[2,5,8]	none	[2,5,8]
6	[2,5,6,8]	2	[5,6,8]
1	[1,5,6,8]	1	[5,6,8]
8	[5,6,8,8]	5	[6,8,8]

The induction claim is about membership: after t arrivals, retain the largest min(k,t) entries. Inserting one value and deleting a minimum preserves it. Duplicate scores consume separate ranks, so the third-largest final value is 6.

for each arrival:
    push it into the min-heap
    if size>k: pop the minimum

The heap-order property alone does not prove this result. A perfectly valid min-heap containing the three smallest scores would satisfy heap order and solve the wrong problem. Admission and eviction establish the retained-set invariant.

Decide whether an entry is a value, a stream head, or a boundary

Top K Frequent changes candidate identity. First aggregate all occurrences, then admit one candidate per distinct value, ranked by final frequency. Keeping individual occurrences would answer a score-rank question again. At a frequency tie, the contract may permit several valid selections.

For pair sums, a different compression applies. Fixing the first-array index creates one sorted stream as the second index advances. Admit only each active stream’s next unreported pair; after consuming a head, admit its successor. The sorted-stream proof explains why hidden entries cannot beat that head. The later workshop separately proves why only the first k rows may need admission.

For a streaming median, one retained top-k set cannot work because the desired rank changes with every insertion. Two heaps instead preserve a partition: every low value <= every high value, with low having equal size or one extra entry. Moving one boundary root repairs size while preserving order. Median queries inspect roots without consuming them.

Feasibility is a filter, not a reward

IPO introduces projects that exist but are not yet affordable. A heap ordered by profit cannot by itself know when to admit them. Sort requirements once, advance a pointer as capital grows, and admit every newly affordable unchosen project. Only then select the largest positive profit. This separates the eligibility proof from the greedy-choice proof.

Use a heap when many small updates are followed by repeated extreme-value decisions. A one-time query may be simpler with sorting or selection. State the expected cost and input-mutation tradeoff before choosing a data structure; the familiar library should not decide the problem for you.

Transfer: find the mistake in a plausible eviction rule

Retain the two most frequent values of [4,4,9,9,9,2,2]. A learner keeps a size-two min-heap ordered by the numeric value itself after counting. What can it return, what selection is actually valid, and what must the priority represent? Does this input expose an incorrect result? If not, construct one that does.

Model answer: priority follows the requested objective

Final counts are 4:2, 9:3, 2:2. The numeric-value rule can keep {4,9}, which happens to be valid here, so this example alone does not expose the bug. Change the input to [1,1,1,8,8,9]: the same rule keeps {8,9}, excluding the most frequent value 1. The required selection is {1,8}.

The priority must be frequency, exposing the weakest retained frequency. For the first input, {9,4} and {9,2} are both valid because of the cutoff tie. A good counterexample changes the factor the wrong rule confuses—numeric value versus frequency—rather than merely making the input larger.

For each exercise, specify candidate identity, admission, priority, eviction or consumption, maximum heap size, and tie policy. These choices carry the proof; Push and Pop only implement them.

Prerequisites and readiness

Know heap push/pop costs, min-heap versus max-heap order, frequency counting, and sorted-stream merging. Be able to state which candidates belong in the heap—not merely which item should be at its root.

Reasoning workshop: the heap is a precisely chosen candidate set

Retain the best by exposing the worst

A learner claims that a valid min-heap of size k must contain the k largest values. Construct a counterexample: for input [1,2,9,10] and k=2, heap [1,2] satisfies heap order and size but has the wrong membership. The missing claim is that no excluded processed entry outranks a retained minimum. The insertion/eviction rule establishes that claim; heap order merely exposes the weakest retained entry. Duplicates are still occurrences: k=4 on [6,5,5,4] returns 4.

Top K Frequent first aggregates occurrences into one entry per distinct value. A cutoff tie creates multiple valid selections: frequencies a:5, b:3, c:3 with k=2 allow {a,b} or {a,c}. Sorting result values cannot resolve that semantic ambiguity. A correct test checks selected count, uniqueness, and frequency dominance over excluded entries.

Merge only the next candidate from each sorted row

For pair sums, row i is nums1[i] paired successively with every nums2 value. It is sorted because nums2 is sorted. Keep the next unreported pair per seeded row. Popping one pair reveals only its successor; eagerly inserting every pair wastes the product-sized search space.

There are two proofs to keep separate. Frontier order: every unseen entry of an active row is at least its head, so the smallest head is the smallest unreported pair among active rows. Replacing that head with its immediate successor restores the invariant without scheduling any index pair twice.

Why some rows can be omitted: let h=min(k,len(A)), with both arrays sorted ascending and B nonempty. If h=len(A), no row is omitted. Otherwise h=k. Any pair from an omitted row i>=k satisfies A[i]+B[j] >= A[k-1]+B[0]. The k distinct index pairs (0,0),...,(k-1,0) are already in seeded rows, and each has a sum no larger. Therefore there is a valid set of k smallest pairs entirely within the seeded rows. This is a rank argument: it does not say omitted rows have strictly greater sums. At a tie, the contract permits either choice.

For A=[1,4,7,10], B=[2,3], k=3, seed sums 3,6,9. Pop (0,0) with sum 3 and reveal (0,1) with sum 4. Pop that 4; its row is exhausted. Next pop (1,0) with sum 6. The omitted row starts at 12, but even when A=[1,1,1,1] and B=[2], seeding the first three rows remains sufficient: three distinct index pairs with tied sum 3 satisfy the query.

With A=[1,1] and B=[2,2], four index pairs all display [1,2]. These are four valid choices of indices, so k>=4 requires four output rows. Deduplicating by displayed values would lose multiplicity. Sorting A supplies the omitted-row proof; sorting B supplies each row's stream order. If either promise is removed, the corresponding discard is no longer justified.

The implementation seeds h entries with individual pushes and emits t=min(k,len(A)*len(B)) pairs. A safe bound is O((h+t) log(h+1)) time and O(h) auxiliary heap space, plus O(t) output storage. The supplied comparator preserves the full mathematical sum of two signed ints so overflow cannot reverse heap order; ordinary wrapped a+b is not a safe comparison key when inputs may span the int range.

Two heaps describe a rank boundary

In MedianFinder, low is a max-heap of the lower half and high a min-heap of the upper half. Maintain all low values <= all high values and len(low) equal to len(high) or one larger. For the stream 5,1,9,2, sorted prefixes have medians 5,3,5,3.5. Rebalancing moves one extreme root across the boundary, preserving order.

An even median is the mean of the boundary roots. Converting two huge opposite ints separately can lose their small difference; adding signed ints first can overflow for the same sign. The revised helper computes the exact sum safely before scaling and rounding. Querying an empty data structure remains outside the supported contract.

Feasibility and reward are different orderings

IPO sorts projects by required capital, advances a pointer as capital grows, and stores affordable profits in a max-heap. Starting with capital 0, requirements [0,1,1], and profits [1,2,3], choose 1 then 3 to finish with 4. Required capital is a threshold, not a fee to subtract.

The exchange argument relies on choosing a profit that leaves at least as much capital as any alternative first choice. Under “at most k,” a nonpositive best profit should not be forced: it cannot improve capital or unlock a higher requirement. The reference stops in that case. The problem guarantees that the maximum final capital fits the target int. Since each chosen profit is positive, capital never decreases; each intermediate capital is a feasible stopping result and is bounded by that guaranteed maximum. The bound applies to the actual arithmetic as well as the final answer.

Reconstruct the invariant before importing a heap

Name the heap contents, priority, admission rule, eviction rule, and maximum size. For top-k, admission is each input candidate and eviction drops the weakest. For pair sums, admission follows a consumed predecessor. For IPO, admission is newly affordable work. For medians, two sets preserve a rank boundary. The same library operations implement four substantially different correctness arguments.

Reconstruction lab and answer key

Kth Largest Element in an Array

A stream summary keeps only the largest two occurrences. Prefixes [1,10,9] and [8,10,9] produce the same summary. If a later query asks for the third-largest value of that past prefix, can the stored state answer it?

Model answer

No. Both summaries retain {9,10}, but the requested third values are 1 and 8. The discarded values became relevant when k changed. Fixed-k retention is sufficient for its original query, not for arbitrary later ranks; supporting those requires retaining additional information or a different data structure.

Top K Frequent Elements

A streaming shortcut evicts low-frequency values before the input ends and then ignores their future occurrences. With k=1, it sees [2,1,1], keeps 2 after the first tie, and permanently discards 1. Why is final frequency counting different?

Model answer

The last 1 raises its final frequency to two, above 2’s frequency one. Early eviction did not justify forgetting future updates. The reference first builds complete frequencies, then ranks fixed candidates. A live frequency-ranking structure would need to track increments and repair candidate priorities; it cannot reuse the fixed-count proof unchanged.

Find K Pairs with Smallest Sums

A different pair-grid search expands both (i+1,j) and (i,j+1) after every pop. Starting at (0,0), show two ways to schedule (1,1). Why does the reference’s seeded-row successor rule need no visited set?

Model answer

Paths (0,0)→(1,0)→(1,1) and (0,0)→(0,1)→(1,1) both schedule that same index pair. A two-direction search must deduplicate indices. The reference seeds each active row at column zero and advances only to its next column, so every pair has one unique predecessor within its row. Equal displayed value pairs from different indices remain distinct outputs.

Find Median from Data Stream

Two heaps have low values {1,100} and high values {2,3}. Each heap individually obeys its own ordering and the sizes match. What wrong median do their roots imply, and which independent invariant is missing?

Model answer

The roots give (100+2)/2=51, but sorting all four values gives [1,2,3,100] and median 2.5. Size balance is insufficient: every low value must be no larger than every high value. Moving a boundary element while preserving that partition is essential; two valid heap structures do not automatically form a valid rank split.

IPO

Change the economic model: starting capital is 4, each project pays its requirement as a fee and then receives a gross reward. For one allowed project, choices (fee 4,reward 5) and (fee 1,reward 4) are affordable. Does choosing the larger reward remain optimal?

Model answer

No. The first leaves 4-4+5=5, while the second leaves 4-1+4=7. Under that changed model, gross reward is not net profit and fees affect resources. The pack’s IPO contract uses requirements only as thresholds and adds the declared profit; its greedy proof cannot be transferred by merely renaming the inputs.

Problems in this module

• Kth Largest Element in an Array
• Top K Frequent Elements
• Find K Pairs with Smallest Sums
• Find Median from Data Stream
• IPO

Interactive checkpoint

Open the Heap / Priority Queue quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable

Earlier-edition pattern links

The opening now derives the choices above before naming individual recipes. These headings preserve prior bookmarks.

Pattern A: Keep top-k with a min-heap

Continue with the current reasoning workshop.

Pattern B: Top-k frequent by count

Continue with the current reasoning workshop.

Pattern C: Pair sums with index heap

Continue with the current reasoning workshop.

Pattern D: Streaming median (two heaps)

Continue with the current reasoning workshop.

Pattern E: Feasible projects with max profit

Continue with the current reasoning workshop.

When to use Heaps (checklist)

Continue with the current reasoning workshop.

Common failures (checklist)

Continue with the current reasoning workshop.

Problem mapping

Continue with the current reasoning workshop.