Intuition What this page isThe parent note taught the two rules. Here we stress-test them. A heap has a small number of distinct situations that can arise — root violations, leaf violations, odd-sized trees where a node has only a left child, insertions that bubble all the way up, insertions that don't move at all, and the trap of confusing a heap with a sorted list. If you can work every cell in the matrix below, nothing an exam or an interview throws at you is new.
Before anything else, one reminder of the machinery you will use in every example — burned into a picture so we never call an index without a picture behind it.
Recall The three index formulas (0-based)left(i) ::: 2i+1
right(i) ::: 2i+2
parent(i) ::: floor((i-1)/2)
Every heap problem is one of these cells . The worked examples that follow are each tagged with the cell they cover, so by the end you have hit all of them.
Cell
Situation
What makes it tricky
A Validate a correct heap
Must check siblings are NOT compared
B Validate a broken heap
Spot the one bad parent–child pair
C Node with only a left child (odd n)
right(i) ≥ n → must skip, not crash
D Sift-down from the root (max-heapify)
Choose the larger child each step
E Insert that doesn't move (sift-up ends immediately)
Parent already dominates
F Insert that bubbles to the root (full path)
Longest possible sift-up
G Degenerate inputs: n=0, n=1, all-equalEmpty/single-node/ties are all valid heaps
H Word problem (real-world priority queue)Translate a story into heap ops
I Exam twist : "is this array sorted ⇒ is it a heap?" and vice-versaThe sorted↔heap confusion
Forecast for yourself as you read: which cell do you find hardest ? Most people miss C (the missing right child) and I (sorted vs heap). Watch those two.
Worked example 1 — Cell A: validate a correct max-heap[9, 5, 8, 1, 4, 7]
Forecast: guess valid or invalid before reading. (Hint: note that child 5 is smaller than the other subtree's 8 — does that matter?)
List the parents. With n = 6 parent ( n − 1 ) = parent ( 5 ) = ⌊ 4/2 ⌋ = 2 0 , 1 , 2 3 , 4 , 5 Why this step? leaves have no children — checking them is wasted work.Check i = 0 children at 2 ( 0 ) + 1 = 1 2 ( 0 ) + 2 = 2 9 ≥ 5 9 ≥ 8 Why? root must dominate both children.Check i = 1 children at 3 4 5 ≥ 1 5 ≥ 4 Check i = 2 left at 5 8 ≥ 7 6 ≥ n skip .
Verify: every parent ≥ each of its children ⇒ valid max-heap . The fact that node 5 < the far-away 8 is irrelevant — siblings and cousins are never compared .
Worked example 2 — Cell B: validate a broken heap[9, 5, 8, 10, 4, 7]
Forecast: where's the crime?
Parents = 0 , 1 , 2 n = 6 Why? same size, same layout.
i = 0 9 ≥ 5 9 ≥ 8 i = 1 3 10 ), 4 5 ≥ 10 FALSE . Violation found.
Verify: child 10 > parent 5. In a max-heap the biggest value can never sit below a smaller one, so this is invalid . (Fix: 10 would need to sift up — see Example 6.)
Worked example 3 — Cell C: the missing right child[20, 15, 18, 9, 11]
Forecast: n = 5
Last parent = parent ( 4 ) = ⌊ 3/2 ⌋ = 1 = 0 , 1 Why fewer parents? only 5 nodes, so most are leaves.i = 0 1 2 20 ≥ 15 20 ≥ 18 i = 1 = 2 ( 1 ) + 1 = 3 = 2 ( 1 ) + 2 = 4 < n = 5 does have two children here. 15 ≥ 9 15 ≥ 11 Now the real single-child case: node i = 2 = 2 ( 2 ) + 1 = 5 5 < n = 5 No — 5 ≥ n no children at all (it's a leaf) and we skip it entirely. Why the guard matters: if we blindly read A[5] we index past the array and crash.
Verify: all checked parents satisfy ≥ child < n correctly stopped us. Valid max-heap. (Note: the "only left child" node in a general heap is whichever node has 2 i + 1 < n ≤ 2 i + 2 n never such a node — the last parent always has two children — and when n even exactly one node has a lone left child. Here n
Worked example 4 — Cell C (even n, lone left child)[20, 15, 18, 9]
Forecast: now n = 4
Last parent = parent ( 3 ) = ⌊ 2/2 ⌋ = 1 = 0 , 1
i = 0 1 2 20 ≥ 15 , 20 ≥ 18 i = 1 = 3 15 ≥ 9 = 2 ( 1 ) + 2 = 4 4 < n = 4 No → node 1 has only a left child . Skip the right. Why? 2 i + 2 ≥ n
Verify: valid. This is the exact case beginners crash on — guard every child access with < n.
Worked example 5 — Cell D: max-heapify (sift-down) from the root[3, 9, 8, 5, 4]
Forecast: the root 3 is clearly too small. How many swaps before it settles?
i = 0 Largest child = 9 at index 1. 3 < 9 [9,3,8,5,4]. Why swap with the larger child? if we swapped with 8 instead, 9 would still sit below 3 — violation persists. Swapping with the max guarantees the new parent 9 dominates the other child 8 for free.Follow the demoted 3 down: now at i = 1 2 ( 1 ) + 1 = 3 4 3 < 5 [9,5,8,3,4].
Follow 3 to i = 3 = 2 ( 3 ) + 1 = 7 ≥ n = 5 stop .
Verify: recheck [9,5,8,3,4]. Parents 0 , 1 i = 0 9 ≥ 5 , 9 ≥ 8 i = 1 9 i = 1 5 ≥ 3 , 5 ≥ 4 Valid. Swaps = 2 = path length ≤ height ⌊ log 2 5 ⌋ = 2 O ( log n )
Worked example 6 — Cell E: insert that DOESN'T move (min-heap) — add 10 to[2,4,3,7,9]
Forecast: 10 is large; in a min -heap large values belong near the bottom. Will it swap at all?
Append at the next free leaf: [2,4,3,7,9,10], new index 5. Why append? the only slot that keeps the tree complete (shape property) is the next array cell.parent ( 5 ) = ⌊ 4/2 ⌋ = 2 3 ≤ 10 no swap . Done in zero moves.
Verify: [2,4,3,7,9,10] — root 2 is still the minimum, every parent ≤ children. Sift-up can terminate immediately ; not every insert bubbles.
Worked example 7 — Cell F: insert that BUBBLES TO THE ROOT (min-heap) — add 1 to[2,4,3,7,9]
Forecast: 1 is smaller than everything. In a min-heap the smallest must end at the root. How far does it climb?
Append: [2,4,3,7,9,1], index 5.
parent ( 5 ) = 2 3 ≤ 1 No → swap. [2,4,1,7,9,3]. Now 1 is at index 2. Why swap? a child smaller than its parent breaks the min-rule; push the small value up.parent ( 2 ) = ⌊ 1/2 ⌋ = 0 2 ≤ 1 No → swap. [1,4,2,7,9,3]. Now 1 at index 0.Index 0 is the root → stop.
Verify: [1,4,2,7,9,3]. Parents 0 , 1 , 2 i = 0 1 ≤ 4 , 1 ≤ 2 i = 1 4 ≤ 7 , 4 ≤ 9 i = 2 2 ≤ 3 Valid min-heap , 1 at the top. Swaps = 2 = full root path = O ( log n )
Worked example 8 — Cell G: degenerate inputs (empty, single, all-equal)Forecast: is an empty array a valid heap? Is [5,5,5]?
n = 0 []):Vacuously a valid heap (both max and min). Why? the order property is "for all parents…"; with no parents it's trivially true.n = 1 [42]):Valid heap — and 42 is simultaneously the max and the min.All-equal [5,5,5,5]: check i = 0 5 ≥ 5 and 5 ≤ 5 i = 1
Verify: [5,5,5,5] satisfies ≥ and ≤ valid max-heap AND a valid min-heap at once . The rules use ≥ ≤ > <
Worked example 9 — Cell H: word problem (hospital triage priority queue)Statement: An ER uses a min-heap keyed by triage number (1 = most urgent). Currently the wait list, in array form, is [1, 3, 2, 8, 5]. A new patient with triage 2 arrives, and then the doctor calls the most urgent patient. Show the heap after each event.
Forecast: which structure gives instant "who's next?" — and does the new 2 climb?
Model: most-urgent-first = smallest key on top ⇒ a Priority Queue backed by a min-heap. Why a heap? peek-min is O ( 1 ) O ( log n ) Insert 2 (sift-up): append → [1,3,2,8,5,2], index 5. parent ( 5 ) = 2 2 ≤ 2 Yes (ties OK) → no swap. Heap: [1,3,2,8,5,2].Extract-min (call the patient): the root 1 leaves. Move the last leaf 2 (index 5) to the root to keep the shape: [2,3,2,8,5], n = 5 Why move the last leaf? it's the only removal that preserves completeness.Sift-down the new root 2: i = 0 2 at index 2. 2 ≤ 2 2 \le its children already). Stop.
Verify: patient called had triage 1 (the true minimum) ✓. Final heap [2,3,2,8,5]: i = 0 2 ≤ 3 , 2 ≤ 2 i = 1 3 ≤ 8 , 3 ≤ 5 2 = new most-urgent. Two O ( log n )
Worked example 10 — Cell I: exam twist — sorted vs heapStatement: Answer both. (a) Is the ascending-sorted array [1,2,3,4,5,6,7] a valid min-heap ? (b) Is the max-heap [9,5,8,1,4,7] a sorted array?
Forecast: guess "yes/no" for each before checking. Most people get exactly one right.
(a) Sorted ⇒ min-heap? Check parents 0 , 1 , 2 [1,2,3,4,5,6,7]. i = 0 1 ≤ 2 , 1 ≤ 3 i = 1 2 i + 1 = 3 2 i + 2 = 4 2 ≤ 4 , 2 ≤ 5 i = 2 3 ≤ 6 , 3 ≤ 7 Yes — an ascending sorted array is always a valid min-heap. Why? if A A [ i ] ≤ A [ j ] i < j 2 i + 1 , 2 i + 2 > i ≤ (b) Max-heap ⇒ sorted? Read [9,5,8,1,4,7] left to right: 9,5,8 — it goes down then up , not monotone. No. Why? a heap only orders ancestor–descendant, so the array is not sorted; siblings like 5 and 8 can be in any order.
Verify: (a) confirmed valid min-heap; (b) 5 < 8 with 5 before 8 yet 9 before both ⇒ not ascending, not descending ⇒ not sorted . Moral: sorted ⇒ heap, but heap ⇏ sorted . This is Cell I, the classic trap.
Recall One line per cellCell C guard you must never forget? ::: child < n before accessing A[2i+1] or A[2i+2].
When does a node have only a left child? ::: When 2 i + 1 < n ≤ 2 i + 2 n larger child, so the new parent dominates the sibling too.
Is an empty array a valid heap? ::: Yes — vacuously (no parent–child pair to break).
Can one array be both a valid max- and min-heap? ::: Yes, if all elements are equal.
Sorted ascending ⇒ valid min-heap? ::: Yes, always. Heap ⇒ sorted? ::: No.
"Guard the ghost child" (Cell C: check < n) and "Sorted feeds heap, heap won't feed sorted" (Cell I).
Priority Queue — Example 9 is a priority queue in disguise.Heapsort — repeated extract-max on Example 5's result.Build-Heap (Heapify) O(n) — many sift-downs like Example 5, bottom-up.Complete Binary Tree — the shape rule behind "append at the last leaf."Binary Search Tree — Example 10's contrast: a BST would let you search.Big-O Notation — every example's swap count ≤ height = O ( log n )
