Algorithms from zero
Heaps: code reading
Crux Read real heap code and predict behaviour: a sift-up bug, the build-heap loop bound, the top-k size-k heap, and the heapify complexity argument.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skyHeap bugs hide in index arithmetic and loop bounds — a sign flip, an off-by-one in the last non-leaf, a min/max mix-up. Read each snippet the way you would in review: trace the invariant, then pick the precise defect or the correct claim.
Goal
Practise reading heap code at the level a senior engineer reviews it: spot a sift-up that compares the wrong way, justify the build-heap loop bound, confirm the top-k heap is sized and oriented correctly, and defend why heapify is O(n).
Snippet 1 — sift-up
// Intended: min-heap. siftUp restores the property after a push.
function siftUp(heap, i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (heap[i] > heap[parent]) { // <-- comparison
[heap[i], heap[parent]] = [heap[parent], heap[i]];
i = parent;
} else {
break;
}
}
} Quiz
Completed
This is meant to maintain a MIN-heap, but the property breaks after pushes. What is the defect?
Heads-up For a 0-indexed array the parent of i is exactly floor((i-1)/2). floor(i/2) is the 1-indexed formula and would be wrong here. The parent arithmetic is correct; the comparison direction is the bug.
Heads-up At i = 0 you are at the root, which has no parent — stopping at i > 0 is correct. Running to i >= 0 would compute parent of the root and read out of bounds. The real bug is the comparison direction.
Heads-up It swaps when heap[i] > heap[parent], pushing larger values up — that maintains a MAX-heap. For a min-heap the condition must be heap[i] < heap[parent].
Snippet 2 — build-heap
function buildHeap(arr) { // sift-down each non-leaf, bottom-up
const start = Math.floor(arr.length / 2) - 1;
for (let i = start; i >= 0; i--) {
siftDown(arr, i);
}
return arr;
} Quiz
Completed
Why does the loop start at Math.floor(n/2) - 1 and go downward, and what would break if it started at 0 and went upward instead?
Heads-up Indices past floor(n/2)-1 are leaves with no children, so sift-down on them is a no-op — including them only wastes a constant factor, but it is harmless. The real reason for the bound is that processing must be bottom-up so subtrees are already valid; that is what going downward from the last non-leaf guarantees.
Heads-up Bottom-up (from last non-leaf down to root) is the correct heapify. Top-up with sift-down breaks the precondition that a node's subtrees are already heaps, so it can leave the array un-heapified.
Heads-up For 0-indexed arrays the last node is n-1 and its parent is floor((n-1-1)/2) = floor(n/2)-1, which is the last node that has a child. So floor(n/2)-1 is correct.
Snippet 3 — top-k
function topKLargest(nums, k) {
const h = new MinHeap(); // min-heap, root is smallest
for (const x of nums) {
h.push(x);
if (h.size() > k) h.pop(); // drop the current minimum
}
return h.toArray(); // the k largest (heap order)
} Quiz
Completed
For nums = [4, 1, 7, 3, 8, 5] and k = 3, what does the heap hold at the end, and what is the running time?
Heads-up A min-heap is used precisely so the SMALLEST current candidate sits at the root and gets popped when the heap overflows past k. After all pops, the survivors are the k LARGEST: {5, 7, 8}.
Heads-up Insertion order does not decide survival. Each overflow pops the current minimum, so 4 (popped once 5,7,8 dominate) does not survive. The three largest, {5, 7, 8}, remain.
Heads-up The heap never exceeds k+1 elements (it pops back to k on overflow), so each push/pop is O(log k), giving O(n log k) — better than O(n log n) when k ≪ n.
Snippet 4 — heapify complexity
A heap built bottom-up calls sift-down once per non-leaf.
Node counts by height h (n total): ~n/2 at h=0, n/4 at h=1, n/8 at h=2, ...
sift-down cost from a node of height h is O(h).
Total work T(n) = Σ_h (n / 2^(h+1)) · h Quiz
Completed
Evaluating the sum T(n) = Σ_h (n / 2^(h+1)) · h, what is build-heap's complexity, and why is the intuition 'n/2 sift-downs × O(log n) each = O(n log n)' wrong?
Heads-up That treats every internal node as height log n. But ~n/2 are leaves (height 0), ~n/4 height 1, and so on; the weighted sum Σ h/2^h converges, giving O(n), not O(n log n).
Heads-up build-heap touches Θ(n) nodes, so it cannot be sub-linear. The total is O(n) — linear — not O(log n).
Heads-up A heap of n nodes has height ⌈log₂ n⌉, not n, so no node sifts more than O(log n) levels. The weighted sum over heights converges to O(n).
Recap
Heap correctness lives in details you read line by line: sift-up’s comparison must match min vs max (child < parent for a min-heap); build-heap must run bottom-up from the last non-leaf at floor(n/2)-1 so each node’s subtrees are already heaps; top-k uses a size-k MIN-heap and pops the root on overflow, leaving the k largest in O(n log k); and heapify is O(n) because the height-weighted node sum Σ h/2^h converges — most nodes are cheap leaves. Trace the invariant before you trust the code.