Priority Queues with Python `heapq`

The heapq module in the Python standard library implements the heap queue algorithm, also known as a priority queue. A heap is a binary tree stored in a flat list where the smallest item is always at position 0. Use heaps when you need to repeatedly access or remove the smallest (or largest) item from a changing collection.

python

import heapq
 
tasks = []
heapq.heappush(tasks, (3, "Low priority"))
heapq.heappush(tasks, (1, "Urgent"))
heapq.heappush(tasks, (2, "Normal"))
 
while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"{priority}: {task}")

Even though "Low priority" was pushed first, the heap reorders items so heappop always returns the one with the smallest priority number next:

text

1: Urgent
2: Normal
3: Low priority

heappush adds items and maintains heap order. heappop always returns the smallest item. Items are popped in priority order regardless of insertion order.

Pushing and popping

The fundamental heap operations are heappush (add) and heappop (remove smallest), and a plain list becomes a valid heap the moment you run it through heapify.

python

import heapq
 
heap = [5, 2, 8, 1, 9]
heapq.heapify(heap)
print(heap)   # [1, 2, 8, 5, 9]
 
heapq.heappush(heap, 3)
print(heap)   # [1, 2, 3, 5, 9, 8]
 
print(heapq.heappop(heap))   # 1
print(heap[0])                       # 2

heapify transforms a regular list into a heap in O(n) time. The list is rearranged so heap[0] is always the minimum. heappop removes and returns it, restoring heap order.

For combined push-then-pop, use heappushpop (more efficient than separate calls):

python

import heapq
 
heap = [1, 5, 10]
smallest = heapq.heappushpop(heap, 3)
print(smallest)   # 1
print(heap)              # [3, 5, 10]

heappushpop(heap, 3) pushes 3, then pops and returns the smallest (which is still 1). This is more efficient than calling heappush followed by heappop.

Finding the N largest or smallest

nsmallest and nlargest efficiently find the top or bottom N items from any iterable.

python

import heapq
 
scores = [85, 92, 78, 95, 88, 72, 90]
 
print(heapq.nlargest(3, scores))   # [95, 92, 90]
print(heapq.nsmallest(3, scores))  # [72, 78, 85]

For small N relative to the data size, these functions are more efficient than sorting the entire list. For N=1, use min() and max() instead. When N is close to the list size, sorted() is simpler and comparable in performance.

nlargest and nsmallest also accept a key argument:

python

import heapq
 
records = [
    {"name": "Maya", "score": 92},
    {"name": "Devin", "score": 85},
    {"name": "Priya", "score": 95},
]
 
top = heapq.nlargest(2, records, key=lambda r: r["score"])
for r in top:
    print(r["name"])

Priya has the highest score at 95, followed by Maya at 92, so those two names print in that order:

text

Priya
Maya

Min-heap to max-heap

heapq is a min-heap: the smallest value is always at heap[0]. To create a max-heap, negate the values.

python

import heapq
 
scores = [85, 92, 78, 95]
max_heap = []
 
for score in scores:
    heapq.heappush(max_heap, -score)
 
print(-heapq.heappop(max_heap))   # 95
print(-heapq.heappop(max_heap))   # 92

Negate on push (-score) and negate on pop. The largest original value corresponds to the smallest negated value, so it appears at the top of the min-heap.

Using tuples for priority ordering

Store (priority, item) tuples to sort by priority. heapq compares tuples element by element.

python

import heapq
 
events = []
heapq.heappush(events, (2, "task_b"))
heapq.heappush(events, (1, "task_a"))
heapq.heappush(events, (1, "task_c"))
heapq.heappush(events, (3, "task_d"))
 
while events:
    print(heapq.heappop(events))

task_a and task_c share priority 1, so heapq falls back to comparing the strings alphabetically to break the tie, putting task_a first:

text

(1, 'task_a')
(1, 'task_c')
(2, 'task_b')
(3, 'task_d')

When the first element is equal, heapq compares the second element. If the second elements are not comparable (e.g., two objects), add a tie-breaking counter:

python

import heapq
from itertools import count
 
counter = count()
heap = []
heapq.heappush(heap, (2, next(counter), "task_b"))
heapq.heappush(heap, (2, next(counter), "task_a"))

The counter ensures no two entries compare equal on all elements, preventing TypeError when priority is the same.

Practical example: task scheduler

Build a simple task scheduler that processes the highest-priority task first. The class wraps a heap so callers never touch the underlying list directly.

python

import heapq
 
class Scheduler:
    def __init__(self):
        self.tasks = []
    def add(self, name, priority):
        heapq.heappush(self.tasks, (priority, name))
    def next(self):
        if self.tasks:
            return heapq.heappop(self.tasks)
        return None
    def peek(self):
        return self.tasks[0] if self.tasks else None

With the class defined, add three tasks out of priority order and confirm they come back out in priority order instead:

python

scheduler = Scheduler()
scheduler.add("Send report", 2)
scheduler.add("Fix bug", 1)
scheduler.add("Review code", 3)
 
print("Next:", scheduler.next())
print("Next:", scheduler.next())
print("Next:", scheduler.next())

Even though "Fix bug" was added second, its priority of 1 puts it first out of the scheduler, ahead of both other tasks:

text

Next: (1, 'Fix bug')
Next: (2, 'Send report')
Next: (3, 'Review code')

Tasks are processed in priority order. heap[0] gives the next task without removing it.

heapq vs queue.PriorityQueue

Use heapq for algorithms, sorting, and single-threaded priority queues. Use queue.PriorityQueue when multiple threads produce and consume items. If you only need a simple FIFO queue without priority ordering, collections.deque is a lighter option.

Common mistakes

Modifying the heap list directly. Never insert, delete, or sort the heap list manually. Use heappush, heappop, and heapify to maintain heap invariants. Direct manipulation breaks the heap property.

Forgetting that heapq is a min-heap. heap[0] is the smallest value. If you need the largest, negate values or use nlargest.

Using nlargest when min() or max() suffices. For N=1, min(data) and max(data) are simpler and faster. Reserve nlargest and nsmallest for N > 1.

Comparing incompatible objects in a heap. heapq compares tuple elements sequentially. If the second element of two tuples is not comparable, push with an explicit tiebreaker like itertools.count or a unique ID.