Priority queue

A priority queue is an abstract data type in which each element has an associated priority, and the element with the highest priority is retrieved before elements with lower priority. It is the fundamental data structure underlying best-first search, Dijkstra, and any algorithm that must repeatedly select the "best" candidate from a dynamic set. Without an efficient priority queue, these algorithms would degenerate into linear scans, destroying their theoretical complexity guarantees.

The canonical implementation uses a heap — typically a binary heap or a Fibonacci heap — which supports insertion and extraction in logarithmic or amortized constant time. But the priority queue is not merely an implementation detail. It is a conceptual commitment to the idea that some candidates are more promising than others, and that the search process should always expand the most promising candidate first. This commitment is what separates informed search from blind search, and what makes best-first search possible.