Priority Queues

A priority queue serves elements by priority rather than arrival order, usually implemented with a binary heap.

Serve by importance, not arrival

A priority queue is an abstract container that always returns the element with the highest priority. Unlike a FIFO queue, arrival order is irrelevant. The core operations are insert with a priority and extract the most urgent element, plus often a decrease-key that raises an element's priority.

How it is built

Kronos motion — classical

The standard implementation is a binary heap, giving O(log n) insert and extract and O(1) peek at the top. Simpler backings exist: an unsorted array gives O(1) insert but O(n) extract, while a sorted array gives O(n) insert but O(1) extract. The heap balances both at O(log n).

Peek highest priority: O(1)
Insert: O(log n)
Extract highest priority: O(log n)
Decrease-key: O(log n)

Where priority queues drive algorithms

Dijkstra's shortest-path algorithm repeatedly extracts the nearest unvisited vertex, and A* extracts the node with the best estimated total cost. Prim's minimum-spanning-tree algorithm picks the cheapest crossing edge. In each case the priority queue is what makes the greedy choice efficient.

Min or max, and changing priorities

A priority queue is either a min-queue or a max-queue depending on whether it serves the smallest or largest priority. Some algorithms also need to change an element's priority after insertion; supporting this efficiently requires a handle or index that locates the element inside the heap, so its position can be found and re-sifted in O(log n) without scanning.

Advanced variants

Fibonacci and pairing heaps offer O(1) amortized decrease-key, which improves the theoretical bound of Dijkstra's algorithm on dense graphs. In practice the constant factors are large, so a plain binary heap is often faster despite the worse asymptotics. A d-ary heap with more children per node shortens the tree and can speed up decrease-key-heavy workloads. Choosing the right variant depends on how often decrease-key is called relative to extract.