Priority Queue
A queue that serves the highest-priority item first instead of the oldest. Almost always backed by a binary heap: O(log n) insert and extract, O(1) peek.
A priority queue's contract is simple: insert items with priorities, and always remove the most urgent one. The arrival order is irrelevant — only priority matters.
The standard implementation is a binary heap, giving O(log n) insert and extract-min/max with O(1) peek. A sorted list would make extraction O(1) but pays O(n) per insert; the heap balances both. Language libraries expose it as PriorityQueue (Java), heapq (Python), or priority_queue (C++).
It appears anywhere "next most important" drives processing: Dijkstra and A* pull the closest frontier node, operating systems schedule the highest-priority task, event-driven simulators pop the earliest event, and Huffman coding repeatedly merges the two rarest symbols.
Operations
| Operation | Complexity |
|---|---|
| peek best | O(1) |
| insert | O(log n) |
| extract best | O(log n) |
| change priority | O(log n) with index |
Where it's used
Schedulers, pathfinding frontiers, event simulation, bandwidth management, top-k streaming, Huffman coding.