8.1 Priority Queue ADT

Priority Queue Fundamentals

A priority queue is an abstract data type that manages elements based on assigned priorities rather than insertion order. Where a regular queue follows First-In-First-Out (FIFO), a priority queue always serves the highest-priority element first. This makes it foundational for algorithms where processing order depends on some ranking, not just when something arrived.

Priority Queue ADT and Operations

The priority queue ADT models a collection where every element has an associated priority value. You can think of it as a queue that constantly reorders itself so the most important item is always at the front.

Core operations:

• Insert(element, priority) — adds an element with its associated priority to the queue
• ExtractMax() / ExtractMin() — removes and returns the element with the highest (max-heap) or lowest (min-heap) priority. Which one you use depends on whether you're working with a max-priority queue or a min-priority queue.
• Peek() — returns the highest- or lowest-priority element without removing it
• IsEmpty() — returns true if the queue contains no elements
• Size() — returns the number of elements currently in the queue

The distinction between max and min variants matters. A max-priority queue extracts the largest key first (useful for task scheduling by importance). A min-priority queue extracts the smallest key first (useful in Dijkstra's algorithm, where you want the vertex with the shortest tentative distance).

Priority vs. Regular Queues

A regular queue follows FIFO: elements are processed in the exact order they were added. There's no concept of priority at all.

A priority queue processes elements based on their priority value. A high-priority element added last will still be served before a low-priority element added first. When two elements share the same priority, they're typically processed in FIFO order among themselves (though this isn't guaranteed by all implementations).

Real-World Applications

Priority queues show up in many core algorithms and systems:

• OS task scheduling — The operating system assigns priority levels to processes. Higher-priority tasks (like handling user input) get CPU time before lower-priority background tasks.
• Event-driven simulations — Events are stored with timestamps as priorities. The simulation always processes the event with the earliest timestamp next, using a min-priority queue.
• Dijkstra's shortest path algorithm — At each step, the algorithm extracts the unvisited vertex with the smallest tentative distance. A min-priority queue makes this extraction $O(\log n)$ instead of $O(n)$.
• Huffman coding — Builds an optimal prefix code for data compression by repeatedly extracting the two lowest-frequency nodes and merging them. A min-priority queue drives this process.
• Prim's minimum spanning tree — Selects the next edge with the minimum weight connecting the tree to a new vertex, again relying on a min-priority queue for efficient extraction.

Time Complexity Across Implementations

How you implement a priority queue dramatically affects performance. Here's the comparison:

Binary heap implementation (the standard choice):

1. Insert: $O(\log n)$
2. ExtractMax/ExtractMin: $O(\log n)$
3. Peek: $O(1)$

Sorted array implementation:

1. Insert: $O(n)$ — you need to shift elements to maintain sorted order
2. ExtractMax/ExtractMin: $O(1)$ — the extreme element is already at one end
3. Peek: $O(1)$

Unsorted array implementation:

1. Insert: $O(1)$ — just append to the end
2. ExtractMax/ExtractMin: $O(n)$ — requires a linear scan to find the extreme element
3. Peek: $O(n)$ — also requires a linear scan

Regular queue (array or linked list):

1. Enqueue: $O(1)$
2. Dequeue: $O(1)$
3. Front: $O(1)$

The binary heap is the go-to implementation because it balances both insert and extract at $O(\log n)$. A sorted array gives you fast extraction but slow insertion. An unsorted array gives you fast insertion but slow extraction. The heap avoids that tradeoff by keeping a partially ordered structure, which is enough to always know the max or min without fully sorting everything.