Priority Queues with heapq

Some algorithms repeatedly need the smallest element: scheduling events by time, retrieving shortest distances in graph algorithms, or processing tasks by importance. A heap is a list representation of a binary tree that satisfies the min-heap rule: each parent is no greater than its children. The smallest item is at index 0, but the whole list is not sorted.

Python’s heapq module provides the standard heap operations.

Core function signatures:

• heapq.heapify(list)

Converts a regular Python list into a valid min-heap in-place, rearranging the elements so the smallest item is always at index 0. heapify builds the heap in linear time. - heapq.heappush(heap, item)

Inserts a new item into the heap while automatically restoring the heap property. The heap property is restored after the push. - heapq.heappop(heap)

Removes and returns the smallest item from the heap. The structure is rebalanced so the next smallest element becomes the new root. - heapq.nsmallest(k, iterable)

Retrieves the k smallest elements from any iterable efficiently. Unlike sorting the entire dataset, it focuses only on the few smallest values—useful for top-k selection or thresholding in large datasets.

Example 1: Processing Tasks by Priority

Imagine a help-desk system where lower numbers mean higher priority (1 = critical, 2 = high, etc.). We can use a heap to always handle the most urgent task first:

import heapq

# (priority, description)
tasks = [
    (3, "Update documentation"),
    (1, "Fix production bug"),
    (2, "Reply to customer emails"),
]

heapq.heapify(tasks)  # turn list into a heap

while tasks:
    priority, description = heapq.heappop(tasks)
    print(f"Handling (priority {priority}): {description}")

Output

Handling (priority 1): Fix production bug
Handling (priority 2): Reply to customer emails
Handling (priority 3): Update documentation

This prints the tasks in priority order—1, then 2, then 3—so the critical bug is fixed first, emails are handled next, and documentation updates come last. For this fixed queue, the smallest priority number is handled first. If priorities tie, Python compares the next tuple field, so descriptions determine the tie order; use an added sequence number when arrival order must be preserved.

Example 2: Selecting the k Smallest Errors

In data science, you might want to inspect the k smallest error values from a large list of model losses, without sorting everything.nsmallest() does this efficiently:

import heapq

errors = [0.42, 0.15, 0.78, 0.05, 0.33]
best = heapq.nsmallest(2, errors)
print(best)

Output

[0.05, 0.15]

It returns the two lowest error values. Instead of sorting the entire list, the nsmallest function efficiently extracts only the values you care about—especially useful when working with large datasets or repeated model evaluations.