What is a binary heap?

A binary heap is a tree-shaped data structure that keeps its smallest, or largest, element always instantly accessible at the top, while still supporting fast insertion and removal, which makes it the natural tool for efficiently tracking the best candidates found so far during HNSW‘s search process.

What property does a binary heap actually maintain, and how does that make it useful?

A binary heap organizes its elements into a tree shape following one consistent rule: every parent element is always smaller, or in a different variant always larger, than its own children, which guarantees that the single smallest, or largest, element in the entire structure always sits right at the top, instantly accessible without any searching. Adding a new element or removing that top element both only require a small, bounded amount of rearranging to restore this ordering rule, rather than needing to reorganize the entire structure from scratch, which is what makes a binary heap efficient for repeatedly asking “what’s currently the best (or worst) element I have” while elements keep getting added and removed over time.

Why is this specific capability exactly what HNSW’s search process needs while it’s actively running?

HNSW‘s search process, covered throughout this site’s coverage of how the algorithm searches step by step, needs to continuously track a running set of the best candidate vectors found so far, checking new candidates against the current worst of those already being tracked, and discarding that current worst whenever a better candidate turns up. A binary heap handles exactly this pattern efficiently: the current worst candidate sits instantly accessible at the top of a heap organized appropriately, letting the search quickly check whether a new candidate is good enough to replace it, and efficiently swap it in when it is, without needing to scan through the entire set of tracked candidates each time.

Why would a simpler structure, like keeping a sorted list of candidates, not work as well for this same purpose?

Keeping a fully sorted list of candidates would make finding the current worst candidate just as fast as a binary heap does, but maintaining that full sorted order after every single insertion or removal would generally require more rearranging work than a binary heap needs, since a binary heap only needs to maintain its weaker “parent versus children” ordering rule rather than a complete, strict overall ordering across every element. This difference matters because HNSW’s search process performs this insert-and-possibly-remove pattern extremely frequently while examining candidates, so the smaller, more efficient rearranging work a binary heap requires adds up to a meaningful real-world performance advantage over maintaining a fully sorted structure instead.

A binary heap’s efficient “always know the current worst, cheaply replace it” behavior is precisely the capability HNSW’s search process leans on to track its best candidates as it explores the graph. From here, the pages on how HNSW searches a graph step by step and on order statistics connect this structure directly back to the search behavior it supports.