Debugging challengeIntermediate
A heap that never reorders
Scenario
A hand-rolled binary heap backs a Dijkstra implementation. The project compiles clean with strict: true, and the unit tests — which push plain numbers — all pass. In production the heap holds { dist, node } entries, and suddenly pop() returns them in an arbitrary wrong order, so Dijkstra settles vertices with non-final distances. Not a single red squiggle anywhere. Find the bug and explain why the compiler let it through.
1class MinHeap {2 private data: any[] = [];3 4 push(x: any): void {5 this.data.push(x);6 let i = this.data.length - 1;7 while (i > 0) {8 const parent = (i - 1) >> 1;9 if (this.data[i] < this.data[parent]) { // objects: always false10 [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];11 i = parent;12 } else break;13 }14 }15 16 pop(): any {17 const top = this.data[0];18 const last = this.data.pop();19 if (this.data.length > 0) {20 this.data[0] = last;21 let i = 0;22 for (;;) {23 const l = 2 * i + 1, r = 2 * i + 2;24 let smallest = i;25 if (l < this.data.length && this.data[l] < this.data[smallest]) smallest = l;26 if (r < this.data.length && this.data[r] < this.data[smallest]) smallest = r;27 if (smallest === i) break;28 [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];29 i = smallest;30 }31 }32 return top;33 }34 35 get size(): number { return this.data.length; }36}37 38const nums = new MinHeap();39[5, 1, 3].forEach((x) => nums.push(x));40console.log(nums.pop(), nums.pop(), nums.pop()); // 1 3 5 — numbers work41 42const pq = new MinHeap();43pq.push({ dist: 5, node: 1 });44pq.push({ dist: 1, node: 2 });45pq.push({ dist: 3, node: 3 });46console.log(pq.pop().dist, pq.pop().dist, pq.pop().dist); // 5 3 1 — expected 1 3 5Your task
- What does
{ dist: 5 } < { dist: 1 }evaluate to in JavaScript, and why? What does that do to every sift comparison in the heap? - The class is written in TypeScript with
stricton. Why doestscnot complain about comparing two objects with<? - Rewrite the heap as a proper generic
MinHeap<T>. What extra constructor argument does it need, and what error wouldtscgive if you kept the raw<comparison onT? pop()on an empty heap returnsundefined. What should its return type say, and what doesanydo to the callers?- State the complexity of
pushandpop, and what the broken version degrades to.
DebuggingImplementationSystematic Reasoning
Work it out
Write your analysis before revealing anything. The self-check below compares it against what a strong answer contains.
Reveal
Progressive — each section builds on the previous one.
The bug
Why it happens
The fix
Edge cases
Complexity
Self-check
Tick what your analysis covered. Be honest — this feeds your readiness profile.