The two structures HNSW rests on·12 min

Build the max-heap

0 / 1

# grade this stage (from your course directory)
npx theinference test --stage max-heap --watch

Now the max-heap for the result set W. It is a min-heap with the comparison reversed: the root is the entry with the largest distance — the worst keeper, the one you evict when a closer result arrives and W is full.

One heap, parameterized by a comparator

A max-heap is a min-heap with the order flipped. The clean move is to parameterize a single heap by a less comparator and instantiate both MinHeap and MaxHeap from it — that is exactly what you will wire into C and W inside SEARCH-LAYER.

What to build

Your task

Implement MaxHeap

Implement MaxHeap in src/heap.ts, then expose runMaxHeap(ops). Same op-log replay as the min-heap, but pops return the furthest entry first.

tests/adapters.ts

export function runMaxHeap(ops: HeapOp[]): number[] {
  // replay ops on a MaxHeap; return the id of each popped (furthest-first) Entry
}

Tie-break stays ascending-id

Even in the max-heap, on equal distance the smaller id pops first. Keeping the tie-break consistent across both heaps is what makes the whole search reproducible — a tie that flips here can flip a result id three chapters later.

How it's graded

Adapter mode: the popped-id sequence is compared exactly to the reference for the same fixed op log used by the min-heap.

Build the min-heap The level dice