Priority queues and applications
Sometimes the next item to process should be the most important, not the oldest. A priority queue always hands back the item with the highest (or lowest) priority.
The priority queue ADT
A priority queue supports insert(item, priority), extract-min (or extract-max), which removes and returns the item with the best priority, and peek. Unlike a queue, arrival order does not matter, only priority. Hospital emergency triage is a real-world example: the most urgent patient is seen first.
Naive implementations
With an unsorted array, insertion is O(1) but extract-min scans everything, O(n). With a sorted array, extract-min is O(1) but insertion must shift elements, O(n). Either way, n operations can cost O(n^2). A binary heap, covered in a later unit, does both in O(log n).
Library support
Most languages provide heap-based priority queues: Python's heapq module (a min-heap on a list), Java's PriorityQueue, and C++'s std::priority_queue (a max-heap by default). For items with equal priority, adding a counter as a tie-breaker keeps ordering stable and avoids comparing items that cannot be compared.
Scheduling and simulation
Operating systems schedule tasks by priority. Discrete-event simulations keep events in a priority queue keyed by time, always processing the earliest event next, whether modelling bank queues, network traffic, or epidemics. Job schedulers and timers use the same idea.
Graph algorithms
Dijkstra's shortest-path algorithm repeatedly extracts the unvisited vertex with the smallest tentative distance from a priority queue. Prim's minimum spanning tree algorithm uses one to pick the cheapest edge leaving the tree. A* search, used in games and robotics, orders states by cost so far plus an estimate of remaining cost.
Top-k and merging
To find the k largest of n items, keep a min-heap of size k: each new item larger than the heap's minimum replaces it, costing O(n log k) total. To merge k sorted lists, keep the current front of each list in a min-heap and repeatedly extract the smallest, costing O(n log k) for n total items.
Monotonic stacks and queues
A related family of techniques keeps a stack or deque whose contents stay sorted. A monotonic stack finds, for every element, the next greater element in one pass: push indexes, and pop any whose value is smaller than the current element, recording the current element as their answer. Each index is pushed and popped once: O(n).
Worked example
Find the 3 largest of [7, 2, 9, 4, 11, 5] with a min-heap of size 3. Insert 7, 2, 9: heap {2, 7, 9}. 4 > min 2: replace, {4, 7, 9}. 11 > 4: replace, {7, 9, 11}. 5 < 7: skip. Result: 7, 9, and 11. Only 3 items were ever stored, which is why the method suits huge streams of data.
Key takeaways
A priority queue returns the highest-priority item regardless of arrival order. Unsorted or sorted arrays make one operation O(n); heaps make insert and extract O(log n). Use heapq, PriorityQueue, or std::priority_queue, with tie-breakers. Priority queues drive scheduling, event simulation, Dijkstra, Prim, and A*. Size-k heaps find top-k items and merge k sorted lists in O(n log k). Monotonic stacks solve next-greater-element problems in O(n).
Flashcard
Returns the item with the best priority
Check your understanding
Why is a size-k min-heap good for finding the 10 largest values in a stream of a billion numbers?