The two structures HNSW rests on·5 min
Candidates and results
0 / 1
HNSW's search keeps two priority queues over (distance, id) pairs. C (candidates) is a min-heap: always pop the nearest unexplored node next — that's the greedy part. W (results / working set) is a max-heap: the furthest of the current best-k sits on top so you can evict it cheaply when something better arrives.
Why two orderings
You explore from the nearest candidate (min-heap pop) because that is the greedy bet. But you keep the best results, and the only one you ever throw away is the worst keeper — which is exactly the top of a max-heap. Two opposite orderings, each O(log n) for the one operation it is asked to do.
Min-heap (C) vs max-heap (W) over (dist, id)
C (min-heap) W (max-heap)
pop = NEAREST pop = FURTHEST
(1.2, 7) (9.8, 3) <- evict this when W is full
/ \ / \
(3.0,2) (4.1,9) (5.0,1) (6.2,8)
tie-break: equal distance -> SMALLER id is "nearer"