A priority queue makes one promise that a regular queue does not: whatever you ask for next is the highest-priority item currently in the structure, regardless of when it arrived. A regular queue hands back the oldest item; a priority queue hands back the most important one. That single change in contract is why it needs a different implementation underneath.
What changed in 2026
- Priority queues remain the default answer for best-first search. Dijkstra, A*, and their variants still lean on a binary heap as the standard implementation, and that has not changed.
- Indexed and pairing heaps see more use in performance-sensitive routing and simulation code, specifically because a plain binary heap does not support an efficient decrease-key operation.
- Language standard libraries keep the interface simple. Python
heapq, Java PriorityQueue, and C++ priority_queue all remain thin wrappers around a binary heap array, a pragmatic default rather than something exotic.
What a priority queue actually promises
Two operations define it: insert an item with a priority, and extract the item with the highest (or lowest) priority. Insertion order does not matter at all. Everything else — how it is stored internally — is an implementation detail.
The binary heap: the standard implementation
A binary heap is a complete binary tree stored flat in an array. For a node at index i, its children live at 2i + 1 and 2i + 2. The heap property says every parent is more extreme (smaller, for a min-heap) than its children — note this is weaker than full sorting, which is exactly why it is cheaper to maintain.
import heapq
pq = []
heapq.heappush(pq, (2, "task-b"))
heapq.heappush(pq, (1, "task-a"))
heapq.heappush(pq, (3, "task-c"))
while pq:
priority, task = heapq.heappop(pq)
print(priority, task) # 1 task-a, then 2 task-b, then 3 task-c
Python heapq is a min-heap only. For max-heap behavior, negate the priority values before pushing.
Priority queue operations and complexity
| Operation |
Binary heap |
Unsorted array |
Sorted array |
| Insert |
O(log n) |
O(1) |
O(n) |
| Peek highest priority |
O(1) |
O(n) |
O(1) |
| Extract highest priority |
O(log n) |
O(n) |
O(n), shifting elements |
| Build from n items |
O(n) |
O(1) |
O(n log n) |
Real-world use cases
The Dijkstra shortest-path algorithm always expands the closest unvisited node next — a priority queue is what makes finding "closest" cheap to repeat. A* search uses the same structure with priority equal to cost-so-far plus a heuristic estimate. Operating system schedulers use priority to decide which process runs next. Event-driven simulations process events strictly in timestamp order. Huffman coding repeatedly merges the two lowest-frequency nodes, which is a priority queue extraction in a loop.
Common pitfalls
Forgetting heapq is min-heap only. Pushing raw priorities when you actually want largest-first silently gives you the smallest first instead.
Needing to change the priority of an item after insertion. A plain binary heap does not support this efficiently — you need lazy deletion (push a new entry, mark the old one stale) or an indexed heap.
Assuming a priority queue is fully sorted. Only the top item is guaranteed accessible in O(1); the rest of the internal array is not in sorted order.
Reaching for one when a regular queue would do. The O(log n) overhead is wasted if every item genuinely has equal priority.
FAQ
Is a priority queue the same thing as a heap?
No — priority queue is the abstract interface (insert, get-highest-priority); a heap is the most common way to implement that interface efficiently. A balanced tree like a red-black tree can implement one too, at the cost of more complexity, when arbitrary deletion needs to be efficient.
What happens when two items have the same priority?
Behavior on ties is implementation-defined and often does not preserve insertion order. If FIFO among equal priorities matters, add a secondary tiebreaker such as an insertion sequence number.
How do I get max-heap behavior in Python?
Negate the priority values before pushing, or wrap each item in a small class with a reversed comparison.
Why not just keep the list sorted?
Sorting is O(n log n) every time, even when only one item is added or removed. A heap keeps insert and extract at O(log n) without re-sorting anything.
Where to go next