Question 1

Why are push and pop O(log n)? Not what — why.

Accepted Answer

Both walk one root-to-leaf path, and completeness pins the height at floor(log₂ n). A sift touches one node per level and stops as soon as the promise holds, so its cost is bounded by the height. Completeness — every level full except the last, which fills left to right — forces the height to floor(log₂ n) for n nodes, and that is where the logarithm comes from. Peek stays O(1) because the maximum is simply the root, never searched for.

Question 2

Follow-up: can you build a heap from n values faster than pushing them one at a time?

Accepted Answer

Yes — sift down from the middle of the array outward, which totals O(n) rather than O(n log n). Pushing pays the height from the top for every element, but sifting down pays height from the bottom, where most nodes live: half are leaves and sift zero levels, a quarter sift at most one, an eighth at most two. The series sums to 2n, so the whole build is linear. Prism animates the push-by-push build because that is what a live priority queue does, but the O(n) construction is the expected answer when the values are all present up front.

Question 3

Follow-up: if building is O(n), can you get a sorted array out of a heap for less than O(n log n)?

Accepted Answer

No — draining it is n pops at O(log n) each, which is exactly heapsort’s bound. Extracting everything from a heap in order is heapsort, and no cheap build can rescue it below n log n — the sorting bound applies to the output, not to the structure. The practical reading is a selection rule: if you need every element ordered, sort; if you need the top few or a live priority order, use the heap and never pay for the rest. That is the whole reason the structure exists.

Question 4

What does a push cost when the new value is smaller than its parent?

Accepted Answer

One comparison and no swaps — O(1), which is the common case on random input. The sift-up loop tests the newcomer against its parent, fails immediately, and exits — one comparison, zero swaps. On random input roughly half of all pushes end this way, which is why heap insertion is much cheaper in practice than its worst case suggests. The trace shows it plainly when a small value arrives: a single compare step, then straight to the unmark.

Question 5

What does the heap property actually promise about the values below the root?

Accepted Answer

Only that each parent outranks its own two children — siblings and cousins are unordered. One local promise, applied everywhere, is the entire structure — and it is deliberately weak, because weak promises are cheap to maintain. It is exactly strong enough to force the maximum to the root by transitivity, and no stronger. The player says this out loud at the moment the build finishes, while the second level visibly disproves sortedness.

Question 6

Why must a heap be a complete tree — every level full, the last filled left to right?

Accepted Answer

Because completeness is what lets the tree pack into an array with no pointers. A gapless level-order layout means the children of slot i sit at fixed arithmetic offsets, so structure becomes index maths — no nodes, no allocation, excellent cache behaviour. It also pins the height at floor(log₂ n), which is where the O(log n) bounds come from. This is why push appends at the next free slot and pop promotes the LAST value rather than a child: both moves preserve the shape first and fix the order second.

Question 7

A pop removes the root. Which value takes its place before the sift-down begins?

Accepted Answer

The value in the last occupied slot, which is then removed from the end. The last slot is chosen purely to preserve the shape: removing the final element is the only deletion that cannot leave a gap. That stand-in is almost certainly a poor root, which is exactly why the sift-down follows. Shape first, order second — the same discipline as push, run in the opposite direction.

Question 8

A sift-down swaps with the first child that outranks the sinking value. What breaks?

Accepted Answer

If the smaller child rises, it becomes the parent of its larger sibling and violates the promise. Whichever child rises inherits the other as its own child, so it must outrank both — and only the larger one does. Swapping with the smaller child produces a violation one level below the repair, which then goes unnoticed because the sift has already moved past it. This is the single most common heap bug, and it is why the player asks you to pick the child before showing the swap.

Question 9

Code stores the heap in a 0-based array but computes the parent as `i / 2`. What is the symptom?

Accepted Answer

Nodes sift toward the wrong ancestors, so the root is often not the maximum. With 0-based indices the parent of `i` is `(i - 1) >> 1`; `i / 2` is the 1-based formula and picks a different node almost everywhere. The sift then compares against a stranger, leaves genuine violations in place, and produces a structure that looks like a heap and is not one. Pick a convention, write both formulas down before coding, and test that the root really is the maximum after a randomised build.

Question 10

Where is the second-largest value in a max-heap of n distinct values?

Accepted Answer

One of the root’s two children — which one is unknowable without comparing them. Every node other than the root is dominated by its parent, so the runner-up can only be a node whose parent is the root itself. That narrows it to two candidates and one comparison — the standard follow-up, and a neat demonstration that the heap property is a chain of local facts. The third-largest is genuinely harder, because it can hide two levels down under either child.

Question 11

What happens when values are pushed into a max-heap in strictly ascending order?

Accepted Answer

Every push sifts all the way to the root — the worst case, but still only log n per push. Each new value is the largest so far, so it climbs the entire path to the root — the maximum work a push can do. Prism records 142 steps for ascending input against 101 for random at the same size, which is the constant factor, not a change of bound. This is the structural difference worth stating out loud: a heap has no degenerate shape, only a degenerate constant.

Question 12

A balanced BST also gives O(log n) insert and O(log n) minimum. Why use a heap at all?

Accepted Answer

It does strictly less work: no ordering between subtrees, no pointers, and no rebalancing. Both give the bound, but the heap gets there with a weaker promise, which makes it cheaper in every constant that matters: contiguous array storage, no allocation per element, no rotations. What you give up is everything ordered — no in-order iteration, no range queries, no floor or ceiling. Choose the heap when the only question you ever ask is "what is the extreme", and the tree the moment you need a second kind of question.

Question 13

You need the 100 largest values from a billion-element stream. Which heap, and how big?

Accepted Answer

A min-heap of size 100: push each value, and pop whenever the size exceeds k. The counterintuitive move is to invert the heap: a min-heap of size k keeps the weakest survivor exposed at the root, so each new value needs one comparison to be rejected, and an accepted one costs O(log k). Total cost is O(n log k) time and O(k) space, with the stream never stored. Reach for the opposite extreme from the one the question names — that inversion is the point of the exercise.

Question 14

Follow-up: now an item already in the queue gets a better priority, as in Dijkstra. What do you do?

Accepted Answer

Push the improved entry again and discard stale pops, or keep an index to sift the item in place. A bare heap cannot locate an arbitrary element, so there are two standard repairs: carry a value-to-index map and sift from that index, or push duplicates and skip entries already finalised when they pop. Lazy deletion is what most production Dijkstra implementations do, because the map costs code and the duplicates cost only a bounded amount of memory. Prism’s Dijkstra and Prim traces narrate exactly that discard.

Question 15

Explain a heap to someone who does not code. Say it out loud before revealing.

Accepted Answer

Think of a company org chart with exactly one rule: nobody may outrank their own boss. That is the whole rule — it says nothing about how two people in different departments compare. It is still enough to guarantee that the most senior person in the entire company is sitting at the very top, and you can read that off instantly without asking anyone. When someone new joins, they take the next free desk at the bottom, and then they get promoted past each boss they outrank until they hit one who genuinely outranks them — a handful of steps, not a reorganisation. When the person at the top leaves, you do not promote their deputy, because that would leave a hole in the middle of the seating plan; you move the most junior person into the top chair and let them sink back down, always swapping with the more senior of their two subordinates. Where the picture misleads: people want the chart to be a ranking, and it is not. Ask a heap for the third most senior person and it has no idea — it would have to go and look. It answers exactly one question fast, and refuses everything else, which is precisely why it is cheap.. The test is whether the listener understands why so weak a rule is worth having. A strong answer names the one promise, shows both repairs as short walks, and admits what the structure refuses to tell you.

Heap operations — every question, written out