215: Heaps and Priority Queues

Learning outcomes

By the end of this lesson, you can:

explain and apply the heap invariant in a realistic implementation;
explain and apply array representation in a realistic implementation;
explain and apply sift operations in a realistic implementation;
explain and apply heapify in a realistic implementation;
explain and apply top-k selection in a realistic implementation.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before you start, retrieve one concrete example from an earlier project in which you had to manage a changing priority, select a small set of best results, or process work in a particular order. The point is not to memorize heap terminology. It is to make a defensible choice in an interview-sized problem and in a production data-processing problem, where the right approach depends on the constraints rather than on a memorized template.

Terminology

Heap invariant: In a min-heap, every parent is no greater than either child. That guarantees that the root is globally minimal, but it does not sort the rest of the elements.
Array representation: A binary heap can live compactly in an array through parent and child index formulas. This avoids per-node allocations and generally gives the implementation good memory locality.
Sift operations: An insertion appends a value and then sifts it up. An extraction moves the root to the end, removes that element, and sifts the replacement root down.
Heapify: Building a heap bottom-up from an existing array takes O(n), rather than O(n log n), because most nodes are close to the leaves and can move only a short distance.
Top-K: Keep a heap of size k while scanning n items to obtain O(n log k) selection. When k is small, this can avoid the cost of sorting all n items.
Priority updates: A classic heap cannot efficiently find and update an arbitrary item by value. Supporting an operation such as decrease-key requires an index or handle map, or a strategy such as inserting a new entry and ignoring stale entries later.

Mental model

Treat Heaps and Priority Queues as a design problem with observable inputs, outputs, invariants, and failure modes. A heap preserves only enough order to expose an extreme element efficiently. It does not maintain a fully sorted collection. That limited ordering is exactly why heaps work well for schedulers, top-K queries, graph algorithms, and streaming selection.

The useful question is not simply, “Can I use a heap here?” Ask instead which ordering guarantee the caller needs, how often the extreme value changes, how much memory is available, and what happens when an item is missing, duplicated, retried, or made stale. A strong implementation makes those assumptions visible and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to show why the design is safe.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true. Then choose the representation and operations that preserve that property. This makes it easier to tell whether a bug is in the heap itself, in the comparison function, or at the boundary where data enters the system.

Deep dive

1. Heap invariant

When a caller needs the smallest item immediately but does not need every item sorted, a full sort is more work than necessary. A min-heap maintains a weaker and more targeted guarantee: every parent is no greater than its children. Consequently, the root is globally minimal. Siblings and separate subtrees are not fully ordered, so reading the array from left to right is not the same as reading sorted output.

Decision rule: Use the heap invariant deliberately when it makes the contract or invariant easier to state and prove. If the data already needs complete ordering, or if a heap would merely reduce typing while hiding an assumption, choose the more explicit design instead.

2. Array representation

A binary heap does not need a tree node object for every value. Store the nodes in an array and use their positions to recover the tree relationships. With zero-based indexing, the parent of index i is Math.floor((i - 1) / 2), while the children are at 2 * i + 1 and 2 * i + 2. The root is at index 0.

This representation is compact, avoids pointer and node-allocation overhead, and usually improves locality because related values are close in memory. The formulas are part of the implementation contract, though: an off-by-one error can silently compare the wrong elements and break the heap invariant.

Decision rule: Use array representation deliberately when its compactness and index formulas make the invariant easier to enforce and inspect. If the surrounding problem requires arbitrary tree navigation or frequent structural changes that do not fit the complete-tree shape, a different representation may communicate the design more clearly.

3. Sift operations

Insertion preserves the complete-tree shape by appending the new value at the end of the array. That new value may be smaller than its parent, so compare it upward and swap until the parent is no greater than it, or until the value reaches the root. This is sift up.

Extraction removes the root, which is the value the caller wants. Move the last array element into the root position, shrink the array, and compare that replacement with its smaller child. Swap downward until the parent is no greater than both children. This is sift down. Each operation follows at most the height of the heap, so insertion and extraction are O(log n), while peeking at the root is O(1).

Decision rule: Use sift operations deliberately when the operation contract clearly identifies the element that may violate the invariant. Keep the comparison and stopping conditions explicit; a loop that swaps with the wrong child or stops after checking only one child is a common source of subtle ordering bugs.

4. Heapify

If values already exist in an array, repeatedly inserting them performs a sift-up for every value and costs O(n log n) in the usual bound. Bottom-up heapify is more efficient. The leaves are already valid one-element heaps, so start at the last internal node and sift each internal node down toward the leaves.

Although an individual sift down can cost O(log n), most nodes are near the leaves and therefore have very little distance to travel. Summed across all nodes, the work is O(n), not O(n log n). This distinction matters when loading a large batch before processing it.

Decision rule: Use heapify deliberately when you have a batch of values and need to establish the heap invariant once. Use repeated insertion when values arrive incrementally or when the simpler streaming behavior is the actual requirement.

5. Top-K

Sorting all n values is a straightforward way to find the largest or smallest k, but it imposes a cost on values that will never appear in the answer. For top-K largest values, maintain a min-heap containing the current k candidates. Add a value while the heap is not full. Once it is full, compare the new value with the root, which is the smallest candidate: replace the root only when the new value is larger, then sift down.

The heap never grows beyond k, so scanning n values costs O(n log k) and uses O(k) additional space. Decide how ties should behave before implementing: “largest values” may preserve duplicate values, while “top K distinct values” requires a separate uniqueness rule.

Decision rule: Use top-k deliberately when k is small relative to n, especially for streaming or memory-bounded input. If k is close to n, a full sort may be simpler and competitive. Be precise about whether the result itself must be sorted after selection; the heap invariant alone does not provide that final ordering.

6. Priority updates

A heap is good at finding the current extreme, not at locating an arbitrary item. If a task’s priority changes, a classic heap has no direct way to find that task by value without scanning the array. An index or handle map can support efficient updates, but it adds bookkeeping that must stay consistent whenever elements swap.

Dijkstra implementations often choose a simpler alternative: insert a new (distance, vertex) entry whenever a shorter distance is found, then ignore a popped entry if its distance is stale compared with the current best-known distance. This may leave duplicates in the heap, so the implementation must explicitly detect and skip stale entries.

Decision rule: Use priority updates deliberately when the update operation is frequent enough to justify an index or handle map. If duplicate entries are acceptable and stale-entry checks are easy to prove, lazy invalidation can be the smaller design. In either case, document which priority is authoritative and how obsolete entries are recognized.

Worked example

Consider an interview-sized problem and a production data-processing problem. The learner must reason from constraints rather than copy a template. Start by writing the requirement in one sentence, list the input and output contracts, and identify which concept above owns each possible failure mode. For a heap, that includes the comparison direction, treatment of duplicates, behavior for an empty heap, and whether priorities can change after insertion.

Keep the system boundaries separate while doing this analysis: parsing and validation belong at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing those concerns can make a happy-path demo look shorter, but it makes heap edge cases and recovery behavior much harder to reason about.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

This small function is intentionally not a heap implementation. It is a reminder to state the invariant before selecting a data structure. Here the running invariant is that answer is the greatest value seen so far. If the requirement changes to “keep the largest 10 values while processing an unbounded stream,” a bounded min-heap becomes relevant; if the requirement is simply the maximum of a finite array, a single running value is clearer.

Walk the example through at least four cases: the normal path; an empty or missing value; a duplicate, retry, or concurrent path where that distinction is relevant; and a dependency failure. For each case, state which layer detects the problem and what the caller observes. This is the level of explanation expected in a senior code review or technical interview. For heap code specifically, also inspect whether a failed comparison or stale entry can violate the invariant rather than assuming the data structure is at fault.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failures, stale clients, concurrent requests, malformed data, schema changes, and high-cardinality workloads. A priority queue may be correct in isolation but still produce surprising behavior if retries enqueue duplicate jobs, workers disagree about priority, or the queue has no bounded-memory policy. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after evidence identifies the bottleneck or risk.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and all network input is untrusted. A heap does not validate its inputs, make a distributed queue durable, or provide authorization; those guarantees belong to the surrounding system.

Guided lab

Implement a binary min-heap and a priority queue. Use the heap for top-K largest values and for a task scheduler. Test duplicate values, and compare heapify with repeated insertion. As you implement, keep the representation and invariant visible enough that a failing test can tell you whether the problem is in indexing, comparison, or operation ordering.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the comparison, record the work performed and the memory used, not only the final result. Repeated insertion and bottom-up heapify should produce equivalent heap behavior, but they do not have the same construction cost. For the scheduler, decide how equal priorities are handled; if FIFO behavior among equal-priority tasks is required, priority alone is not a sufficient comparison key.

Edge cases and failure modes

Heap invariant: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Confirm after every public mutation that each parent is no greater than its children.
Array representation: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Include empty, one-element, and two-element arrays because boundary indices often expose formula errors.
Sift operations: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Exercise insertion at the root, extraction from a one-element heap, and extraction where the two children have different priorities.
Heapify: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Compare the resulting behavior with repeated insertion and verify the expected O(n) construction strategy rather than only comparing outputs.
Top-K: Test absence, malformed input, duplicates, ordering and concurrency where applicable, and behavior at the smallest and largest credible sizes. Define behavior for k = 0, k > n, negative or invalid k, duplicate values, and an empty input stream.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong. A full sort, an unbounded heap, or a plain maximum may each be correct for one requirement and wrong for another.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values. These can conceal malformed priorities or a comparison function that does not define a stable ordering.
Testing only the happy path and therefore discovering contracts only after integration. Empty heaps, duplicate priorities, stale queue entries, and invalid k values should be specified early.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement. Heapify is not automatically the right choice if values arrive one at a time, and a heap is not automatically better than sorting when k is almost n.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees. A client-rendered priority does not establish the priority the server should process.

For debugging, reproduce the smallest failing case, inspect the actual array after each mutation, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. Check the comparison direction first, then parent and child index formulas, then whether sift down selected the smaller child in a min-heap. For a priority queue with lazy invalidation, log the current authoritative priority and the popped entry so stale-entry handling is observable.

Interview questions

What problem does Heap invariant solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Array representation solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Sift operations solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Heapify solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Top-K solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Heaps and Priority Queues to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. Be ready to explain why the root is guaranteed to be extreme, why the remaining array is not sorted, and how the runtime changes when a bounded heap replaces a full sort.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.