Priority Queues

Overview

A priority queue serves elements by priority rather than insertion order, so the most urgent item comes out first. Backed by a binary heap, it offers O(log n) push and pop with O(1) peek at the top element. Python's heapq and queue.PriorityQueue both implement one, and they power Dijkstra's shortest paths, task schedulers, and event simulations.

Syntax / Usage

Store (priority, item) tuples in a heapq min-heap so the smallest priority pops first.

import heapq

pq = []
heapq.heappush(pq, (2, "email"))    # O(log n)
heapq.heappush(pq, (1, "deploy"))
heapq.heappush(pq, (3, "cleanup"))

priority, item = pq[0]              # peek -> O(1) -> (1, "deploy")

while pq:
    priority, item = heapq.heappop(pq)  # O(log n)
    print(priority, item)
# 1 deploy / 2 email / 3 cleanup

Examples

Add a counter to break ties and keep insertion order stable when priorities match:

import heapq
from itertools import count

pq = []
counter = count()  # unique, increasing tie-breaker

def add(item, priority):
    heapq.heappush(pq, (priority, next(counter), item))

add("b", 1)
add("a", 1)   # same priority, added later -> comes out after "b"

print([heapq.heappop(pq)[2] for _ in range(2)])  # ['b', 'a']

Use a priority queue for Dijkstra's algorithm to always expand the closest node:

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist.get(node, float("inf")):
            continue
        for neighbor, weight in graph[node]:
            nd = d + weight
            if nd < dist.get(neighbor, float("inf")):
                dist[neighbor] = nd
                heapq.heappush(pq, (nd, neighbor))
    return dist

graph = {"a": [("b", 1), ("c", 4)], "b": [("c", 2)], "c": []}
print(dijkstra(graph, "a"))  # {'a': 0, 'b': 1, 'c': 3}

Common Mistakes

• Comparing objects that have no ordering, causing TypeError on tie — add a counter
• Assuming heapq is a max-heap; negate priorities to pop the largest first
• Trying to update a queued item's priority in place instead of pushing a new entry
• Calling heappop on an empty queue, which raises IndexError
• Reaching for queue.PriorityQueue in single-threaded code, paying needless lock overhead

See Also

data-structures-heaps data-structures-queues data-structures-graphs-representation