What is a priority queue?

A priority queue is a data structure that always serves up whichever element currently has the highest priority first, regardless of the order elements were actually added in, and it’s the conceptual role that both the min-heap and max-heap covered elsewhere in this glossary are specifically built to fill during HNSW‘s search process.

What does “priority” actually mean in the context of a priority queue, and how does it differ from an ordinary queue?

An ordinary queue serves elements strictly in the order they were added, first in and first out, with no regard for anything about the elements themselves beyond their arrival order. A priority queue abandons that strict arrival-order rule in favor of always serving whichever element currently ranks highest according to some chosen priority measure, no matter when that element happened to be added relative to the others. For HNSW‘s search specifically, that priority measure is distance to the query, meaning the priority queue’s job is to always hand back whichever tracked candidate is currently closest, or currently furthest, depending on which specific question the search needs answered at that moment.

How do the min-heap and max-heap covered elsewhere in this glossary actually implement this priority-queue concept?

A priority queue is really a conceptual role, describing what behavior is needed, rather than a single specific implementation, and a binary heap, covered elsewhere in this glossary, is simply the most common concrete structure used to actually deliver that behavior efficiently. A min-heap serves as a priority queue where “priority” means smallest distance, exactly matching HNSW’s need to repeatedly pull out whichever unexplored candidate is currently closest and therefore most worth visiting next. A max-heap serves the mirror-image role, acting as a priority queue where “priority” means largest distance, matching HNSW’s need to identify the current weakest tracked result for possible replacement. Both are genuinely priority queues, just built around opposite orderings and serving different specific needs within the same overall search.

Why is it useful to understand the underlying priority-queue concept, rather than just thinking in terms of the specific heap implementations directly?

Framing both structures as priority queues first, and specific heap implementations second, clarifies that what actually matters for HNSW’s search is the behavior being provided, always serving the currently-highest-priority element on demand, rather than any particular implementation detail of how a heap achieves that behavior internally. This distinction matters because a priority queue could in principle be implemented using a different underlying structure entirely, and understanding it at this conceptual level makes it easier to recognize the same underlying need whenever it shows up elsewhere in computing, rather than treating HNSW’s specific use of heaps as an isolated, unrelated detail.

Recognizing both the min-heap and max-heap as specific implementations of the more general priority-queue concept ties together exactly why HNSW’s search relies on them the way it does. From here, the pages on min-heap and on max-heap dig into the two specific implementations this concept gets built from in practice.