Priority Queues in Python: The heapq Module Explained

What a heap is and why a list works as one

A binary heap is a tree where every parent is smaller (or equal to) its children, stored flat in an array using index arithmetic instead of pointers: for index i, the children live at 2i+1 and 2i+2. That's the entire trick behind heapq — it never builds a tree structure, it just maintains this ordering property on an ordinary Python list. The result is that heap[0] is always the smallest element, which is what makes a heap useful as a priority queue: you always know where the next item to process is without scanning anything.

heappush and heappop

Unlike most of the standard library, heapq is a set of functions that operate on a list you own, rather than a class wrapping one:

import heapq

tasks = []
heapq.heappush(tasks, 5)
heapq.heappush(tasks, 1)
heapq.heappush(tasks, 3)

print(tasks)              # [1, 5, 3] -- heap order, not sorted order
print(heapq.heappop(tasks))  # 1, the smallest
print(tasks)               # [3, 5]

Notice that tasks printed as [1, 5, 3], not the fully sorted [1, 3, 5] — a heap only guarantees the root is smallest, not that the whole list is ordered. That relaxed guarantee is exactly why push and pop are cheap: maintaining full sort order on every insert would cost O(n log n) over n inserts, while a heap costs O(n log n) total but each individual push or pop is only O(log n).

Turning an existing list into a heap

If you already have a list of values, heapq.heapify() rearranges it into heap order in place, in linear time — faster than pushing every element one at a time:

values = [9, 4, 7, 1, 5, 2]
heapq.heapify(values)
print(values)              # [1, 4, 2, 9, 5, 7] -- some valid heap order
print(heapq.heappop(values))  # 1

The exact resulting order depends on the algorithm's internal sift-down process and isn't the sorted order — only the property that each parent is no larger than its children is guaranteed. If you need the fully sorted list, call sorted(); if you only need repeated access to the current minimum, heapify() followed by repeated heappop() calls is the right tool, and is what Python's sorting functions are doing something conceptually similar to under the hood in a heapsort variant.

nlargest and nsmallest without a full sort

Sorting an entire million-item list to grab the top five wastes work you don't need. heapq.nlargest() and heapq.nsmallest() maintain a heap of just the size you asked for as they scan the input once:

scores = [88, 45, 99, 67, 72, 31, 95]
top3 = heapq.nlargest(3, scores)
print(top3)   # [99, 95, 88]

people = [{"name": "Ada", "age": 36}, {"name": "Bob", "age": 24}]
oldest = heapq.nsmallest(1, people, key=lambda p: -p["age"])

Both accept a key function just like sorted(), which makes them a drop-in replacement for sorted(data, key=...)[:n] when n is small relative to the size of data. For large n approaching the full list length, a plain sort is competitive or faster, since the constant-factor overhead of maintaining a heap stops paying for itself.

Priority queues with tuples and tie-breaking

A real task queue needs a priority attached to each item, not just a bare number. The idiomatic approach is to push tuples, since Python compares tuples element by element:

import itertools

queue = []
counter = itertools.count()   # tie-breaker, guarantees stable order

def push(priority, item):
    heapq.heappush(queue, (priority, next(counter), item))

push(2, "send email")
push(1, "handle outage")
push(2, "write report")

while queue:
    priority, _, item = heapq.heappop(queue)
    print(priority, item)
# 1 handle outage
# 2 send email
# 2 write report

The counter matters because if two items share a priority, Python falls back to comparing the second tuple element — and if that were the task object itself, comparing two dictionaries or custom objects that don't define ordering raises a TypeError. The counter guarantees a total order that never needs to inspect the actual payload, and as a side effect preserves insertion order among equal priorities, which is usually the behaviour people expect from a queue. The heapq documentation includes a longer worked example of this exact pattern if you want to see variations, such as marking entries as removed instead of deleting them from the middle of the heap.