skip to content

Why must a binary heap be a complete tree with the last level filled left to right?

level: middleimportance: should knowfreq 58%

answer

  1. the heap keeps two invariants, not one
  2. shape exists to serve the representation
  3. what would a gap do to 2i+1?
  4. no gaps means slots 0 to n-1
  5. height is exactly floor(log2 n)

basics

~20 s

Completeness is what makes the implicit array work: nodes fill slots 0 to n-1 with no gaps, so index arithmetic replaces pointers and the height stays floor(log2 n). Allow a hole and child indices address emptiness.

solid answer

~50 s

A heap carries two independent invariants: a **shape** invariant (complete — every level full except the last, which fills left to right) and an **ordering** invariant (parent versus child). The shape one exists to serve the representation. Completeness means the n nodes map exactly onto array slots `0..n-1` with no gaps, so `2i+1` / `2i+2` always name real positions and no pointers, occupancy bits or sentinels are needed. It also pins the height at exactly `floor(log2 n)` — the tightest possible for n nodes — which is where the O(log n) bound on heap operations comes from. If a hole were allowed mid-level you would need either an occupancy check on every access, wasted slots, and a lost height bound (a chain of holes lets depth grow toward n), or a compaction that renumbers every index below the hole.

go deeper

for a junior

Know the shape rule as stated: every level full except the last, which fills from the left. Be able to draw the tree for a seven- or eight-element array without hesitating.

for a middle

Explain that shape and ordering are two separate invariants, and that completeness is what makes slots 0..n-1 gapless so index arithmetic can replace pointers.

for a senior

Argue the consequences: a fixed floor(log2 n) height underwrites every O(log n) bound, and no key order can degrade the shape, unlike a search tree built from sorted input.

for a principal

Be ready to weigh the cost of the shape constraint — contiguous storage, elements that move, no stable handles — against the pointer-based alternative when the workload dictates.

## Two invariants, not one People usually recite only the ordering rule, but a binary heap maintains **two** invariants at all times: 1. **Shape:** the tree is *complete* — every level is entirely full except possibly the last, and the last level's nodes are packed as far left as possible. 2. **Ordering:** every parent compares correctly against both children (`<=` in a min-heap). The ordering invariant is what the structure is *for*. The shape invariant is what makes it *cheap*. Confusing complete with **perfect** (every level full, so `n = 2^(h+1) - 1`) or with **balanced** in the general sense is a common slip: complete is stricter than balanced and looser than perfect, and it is the exact condition the array trick needs. ## What completeness buys **A gapless index space.** Write the tree in level order and the n nodes land in slots `0..n-1` with nothing skipped. That is precisely what lets `left(i) = 2i+1`, `right(i) = 2i+2` and `parent(i) = floor((i-1)/2)` be *total* functions on the occupied range: any computed index is either a real node or `>= n`, and the second case is a single comparison away. No occupancy flag, no null check on a link, no sentinel value carved out of the key space. **No pointers at all.** With gaps you cannot infer position from index, so you would be back to storing links — two or three references per node, plus the allocation each node needs. **A tight, known height.** A complete tree of n nodes has height exactly `floor(log2 n)` measured in edges from the root. It cannot degrade: unlike a search tree, a heap has no insertion order that produces a long thin structure, because shape is maintained explicitly rather than emerging from the keys. Every bound quoted for heap work — the O(log n) path repairs, the O(n log n) of draining the whole structure — rests on that height. **Trivially identified endpoints.** The next free slot is index `n`, and the last node is index `n-1`. Growth and shrinkage touch only the array's tail, which is also why the whole structure can live in one contiguous block that doubles when full. ## What a mid-level hole would cost Suppose you allowed the last-but-one level to have a gap — say slot 5 is empty while slots 6 and 7 hold nodes. Two repairs exist, and both are worse than the rule you just abandoned: - **Keep the gap.** Now `2i+1` may point at an empty slot, so every navigation needs an occupancy test, and every empty slot still consumes memory. Worse, the height guarantee dies: nothing stops a long chain of single-child nodes, and once shape is unconstrained the structure can degrade toward depth `n`, dragging every O(log n) claim with it. - **Close the gap by shifting.** Compaction renumbers every index after the hole, which changes each moved node's parent and children — a wholesale relabelling of the tree, O(n), and it re-parents nodes into positions that may violate the ordering invariant. Both are strictly more expensive than the constant-time alternative completeness gives you: when a node is removed, move the *last* element into the vacated slot and repair one path. That trick is only available because the last element is the one node whose removal cannot break the shape. ## Edge cases the rule must still handle - **Empty heap (n = 0).** No root; `peek` must be a defined error or an explicit "absent" result, and the height is undefined rather than zero. - **Single element (n = 1).** Trivially complete and trivially ordered; index 0 is simultaneously root and leaf, `2*0+1 = 1 >= n`. - **n a power of two.** The last level holds exactly one node, at index `n-1`. This is the shape where a naive "is the last level full?" check most often gets written wrong. - **Perfect tree (n = 2^(h+1) - 1).** Every level full — a special case of complete, not a requirement. ## The takeaway to say out loud Completeness is not an aesthetic property of the diagram; it is the precondition of the representation. It converts "follow a link" into "do arithmetic", converts "allocate a node" into "write a slot", and converts "hope the tree stays short" into a proof that its height is `floor(log2 n)`. A heap that abandons completeness has abandoned the reason to be a heap.

  • Is complete the same as perfect, or as balanced?
    No. Perfect means every level is full, so n must be 2^(h+1) - 1. Balanced only bounds the height to O(log n) with some slack. Complete sits between them: all levels full except the last, which packs left. It is stricter than balanced because it fixes the exact positions, and that exactness is what the index arithmetic needs.
  • Why can a heap never degenerate into a long thin structure the way an unbalanced search tree can?
    Because shape is maintained explicitly rather than derived from key order. Insertion always writes the next free slot and removal always reuses the last one, so the tree is complete by construction regardless of the sequence of keys. There is no adversarial input order that produces a tall structure.
  • Where do the endpoints sit, and why does that matter?
    The next free slot is index n and the last occupied node is index n-1, both O(1) to identify. That is what lets growth and removal touch only the array's tail, keeps the block contiguous, and makes the standard 'move the last element into the vacated slot' repair possible without breaking the shape.

It is stadium seating with no saved seats: fill each row completely and pack the last row from one end, and you can compute where anyone sits from their ticket number alone.

saying these in an interview costs you the question

  • Confuses complete with perfect, demanding full last level
  • Thinks completeness is about key ordering, not shape
  • Believes a heap can degenerate like an unbalanced search tree
  • Says holes are fine if you store a sentinel value
  • Cannot say where the next free slot lives

context

resolving links…