Python Priority Queue Patterns — Core Concepts

Why Priority Queues Matter

Standard FIFO queues treat every item equally. Real systems don’t work that way. A payment failure retry needs to run before a marketing email. A server health check should jump ahead of a log rotation task. Priority queues encode this “what matters most right now” logic directly into your data structure.

Python’s Two Built-in Options

heapq — Low-Level, Fast

The heapq module operates on a plain list, maintaining the heap invariant: the smallest element is always at index 0. It’s not thread-safe, but it’s fast and memory-efficient.

Key operations:

• heapq.heappush(heap, item) — add an item, O(log n)
• heapq.heappop(heap) — remove and return the smallest, O(log n)
• heapq.heappushpop(heap, item) — push then pop in one step, slightly faster than doing both separately
• heapq.nsmallest(k, iterable) — get k smallest items without fully sorting

queue.PriorityQueue — Thread-Safe Wrapper

This wraps heapq with locking, making it safe for multi-threaded producer-consumer setups. It adds blocking get() and put() with optional timeouts.

The Tuple Trick

Both tools compare items directly. The standard pattern is to insert tuples: (priority, item). Lower numbers mean higher priority.

The catch: if two items share the same priority, Python tries to compare the items themselves. If they’re not comparable (like custom objects), you get a TypeError. The fix is a three-tuple with a tiebreaker:

(priority, sequence_number, item)

The sequence number is a monotonically increasing counter that ensures FIFO order among equal priorities and avoids comparing the actual items.

Common Patterns

Task Scheduling

Assign priority levels to different task types. Critical tasks get priority 0, standard tasks get 10, background cleanup gets 50. Workers always pull the most important task first.

Merge K Sorted Streams

heapq.merge() does this natively — it lazily merges multiple sorted iterables into a single sorted stream, using a heap internally. Useful for log aggregation from multiple sources.

Expiring Items

Combine priority queues with timestamps. Set priority to the expiration time. The next item to expire is always at the front. Timer wheels use this pattern extensively.

Rate Limiting with Priority

When you have a rate-limited API and a backlog of requests, a priority queue lets VIP requests go first while staying within the rate limit.

Common Misconception

“A priority queue is just a sorted list.” It’s not. A sorted list maintains full order (O(n) insertion). A heap only guarantees the minimum is at the top (O(log n) insertion). You trade full ordering for speed — and in most real systems, you only need the next item, not a fully sorted view.

When Not to Use Priority Queues

If all your items have the same priority, a regular deque or queue.Queue is simpler and faster. If you need to update priorities of existing items, the standard heapq doesn’t support that well — you’ll need a custom indexed heap or the mark-as-invalid pattern.

One thing to remember: The tuple pattern (priority, tiebreaker, payload) solves 90% of priority queue headaches in Python. Start there.