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 false
10 [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 work
41
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 5

Your task

  1. What does { dist: 5 } < { dist: 1 } evaluate to in JavaScript, and why? What does that do to every sift comparison in the heap?
  2. The class is written in TypeScript with strict on. Why does tsc not complain about comparing two objects with <?
  3. Rewrite the heap as a proper generic MinHeap<T>. What extra constructor argument does it need, and what error would tsc give if you kept the raw < comparison on T?
  4. pop() on an empty heap returns undefined. What should its return type say, and what does any do to the callers?
  5. State the complexity of push and pop, 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.

0/7

Related concepts