Priority queue

A priority queue is an abstract data type where each element has a priority, and removal always returns the highest-priority element (or lowest, depending on convention). Unlike a regular FIFO Queue, the order in which elements come out is determined by their priority, not their insertion time.

Operations

The standard interface:

• insert(item, priority) — add an item with a given priority.
• extractMax() (or extractMin()) — remove and return the highest-priority item. Errors or returns NULL if empty.
• peek() — return the highest-priority item without removing it.
• isEmpty() — state query.

Some priority queues also support:

• changePriority(item, newPriority) — update an existing item’s priority.
• remove(item) — remove a specific item.

Use cases

The “extract the most important next” pattern matches many real-world problems:

• Process scheduling. The OS scheduler picks the next process to run by priority. Real-time systems use priority queues to enforce deadlines.
• Dijkstra’s algorithm. The next vertex to process is the one with the smallest tentative distance.
• A pathfinding*. Pick the next position to expand by lowest estimated total cost.
• Discrete event simulation. Events are processed in time order; the priority queue holds future events.
• Network packet prioritization. Quality-of-service systems extract higher-priority packets first.
• Top-K queries. Maintain a priority queue of size K to track the K largest/smallest items in a stream.
• Huffman coding. Build the encoding tree by repeatedly extracting the two lowest-frequency nodes.

Implementations

The interface is abstract — the underlying data structure can vary:

Implementation	Insert	Extract max	Peek
Unsorted array	$O(1)$	$O(n)$	$O(n)$
Sorted array	$O(n)$	$O(1)$	$O(1)$
Binary heap	$O(\log n)$	$O(\log n)$	$O(1)$
Balanced BST	$O(\log n)$	$O(\log n)$	$O(\log n)$
Fibonacci heap	$O(1)$ amortized	$O(\log n)$ amortized	$O(1)$

The binary heap is the standard implementation — it gives $O(\log n)$ for both critical operations and uses minimal extra memory. See Heap (data structure).

For applications where insertions vastly outnumber extractions (Dijkstra-style), a Fibonacci heap can theoretically improve total time, but the constant factor makes it rarely competitive in practice.

Min vs max priority queue

A max-priority queue extracts the element with the highest priority (largest key). A min-priority queue extracts the smallest. Implementations are symmetric — a max-heap gives a max-PQ; flip the comparison and you have a min-PQ.

In many algorithm presentations:

• “Priority queue” without qualifier often means max-PQ.
• Dijkstra/A*/event simulation typically use min-PQ.
• Top-K-largest typically uses min-PQ of size K (so the smallest in the top-K is at the top, ready to be evicted by anything bigger).

Stability

A priority queue is stable if elements with equal priority come out in insertion order (FIFO). Most heap-based PQs are not stable by default — equal-priority elements can shuffle during heap operations.

To enforce stability, augment each item with a tiebreaker (insertion timestamp, sequence number) and use a priority pair (priority, timestamp).

The Canadian Triage and Acuity Scale is a real-world stability concern: medical priority levels 1–5 (Resuscitation, Emergent, Urgent, Less Urgent, Non-Urgent), where patients within the same level should be served first-come-first-served. A naive max-heap on priority alone can violate this.

Why heaps and not BSTs

Both heaps and balanced BSTs give $O(\log n)$ for the priority queue operations. Why is the heap the standard choice?

• Memory efficiency: heaps store as a flat array, no pointers. BSTs need 2-3 pointers per node.
• Cache locality: array layout dominates linked-tree layout for traversal-heavy workloads.
• Simpler implementation: a heap is just an array with a few index-arithmetic helpers.

BSTs win when you need additional operations beyond priority queue basics — finding arbitrary elements by key, range queries, in-order traversal. Plain priority queues don’t need those.

For the standard implementation, see Heap (data structure). For the queue’s FIFO cousin without priorities, see Queue.