Python heapq: Min-Heap, Priority Queue, and Top-k

Python's heapq module implements a priority queue using a list that follows the min-heap property. The smallest item is always at index zero, but the whole list is not sorted. Use heapify() to transform an existing list, heappush() to add an item, and heappop() to remove and return the smallest item. For top-k selection, compare nsmallest() with sorting based on the size of k.

Contents

Quick answer

Import heapq and call heapq.heapify(values) to build a min-heap in place. Use heapq.heappush(heap, item) and heapq.heappop(heap) for priority-queue operations. Read the smallest item with heap[0] without removing it. Do not iterate the list as if it were sorted.

The official heapq documentation defines the min-heap invariant and the queue operations. A heap is a data structure for repeated smallest-item access, not a general-purpose sorting replacement.

Python heapq min heap diagram showing heapify heappush heappop and nsmallest versus sorting — A heap keeps the smallest item at the root for fast priority operations, but it does not arrange every item in sorted order.

Turn a list into a min-heap

heapify() rearranges a list in place so the smallest value is at the root. It runs in linear time and does not return a new list. Keep the list reference when you call it.

import heapq

values = [7, 2, 9, 1, 5, 3]
heapq.heapify(values)

print(values)
print(values[0])

The internal order is only constrained by the parent-child relationship. Several different list arrangements can represent valid heaps, so tests should check the heap behavior rather than one exact internal layout.

Python Pool infographic showing a heap list, parent-child order, smallest item, and heapq — heapq maintains a min-heap where the smallest item is at index zero.

Push and pop priorities

heappush() adds a value and restores the invariant. heappop() removes and returns the smallest value, then restores the invariant for the remaining items.

import heapq

tasks = [4, 1, 3]
heapq.heapify(tasks)
heapq.heappush(tasks, 2)

next_task = heapq.heappop(tasks)
print(next_task)
print(tasks[0])

For a priority queue with equal priorities, store tuples such as (priority, sequence, item) so ties have a deterministic secondary order and incomparable payloads are not compared directly.

Peek without removing

Index zero is the smallest item in a valid min-heap. Reading it does not change the heap. Check for an empty heap before indexing to avoid IndexError.

import heapq

heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 4)

if heap:
    print("next priority:", heap[0])

Do not call min(heap) repeatedly when the data is maintained as a heap. The root already exposes the smallest item in constant time.

Python Pool infographic mapping tasks through heappush, priority, heappop, and next task — A heap can implement a priority queue with push and pop operations.

Use tuples for task queues

Tuple ordering lets a heap prioritize several fields. Add a monotonically increasing counter when tasks with equal priority may carry objects that cannot be compared.

import heapq
from itertools import count

counter = count()
queue = []

heapq.heappush(queue, (2, next(counter), "write report"))
heapq.heappush(queue, (1, next(counter), "send alert"))
heapq.heappush(queue, (1, next(counter), "refresh cache"))

while queue:
    priority, order, task = heapq.heappop(queue)
    print(priority, order, task)

The counter preserves insertion order within equal priorities. This pattern is useful in schedulers, event queues, and graph algorithms where the payload itself should not determine ordering.

Python Pool infographic comparing nsmallest, nlargest, heap, and top-k results — Use nsmallest or nlargest when only a bounded set of extremes is needed.

Choose nsmallest or sorting

heapq.nsmallest(k, iterable) is useful when k is small compared with the input size. If k is close to the full input size, sorting once can be simpler and competitive. Measure for the actual workload.

import heapq

values = [9, 4, 7, 1, 5, 2, 8]
smallest = heapq.nsmallest(3, values)
sorted_smallest = sorted(values)[:3]

print(smallest)
print(sorted_smallest)

Both results are ordered among the selected values. A heap created with heapify() alone is not an ordered result; use sorted() when the consumer needs a full ordering.

Use max-heaps deliberately

The standard heap is a min-heap. To prioritize larger numbers, store their negatives or wrap the comparison in an object. Negation is easy for numeric priorities but not appropriate for arbitrary payloads.

import heapq

values = [4, 9, 1, 7]
max_heap = [-value for value in values]
heapq.heapify(max_heap)

largest = -heapq.heappop(max_heap)
print(largest)

Keep the sign conversion at the heap boundary so callers do not confuse stored negative priorities with the original values.

Python Pool infographic testing tuples, tie-breaking, mutation, empty heaps, and validation — Check tuple tie-breaking, empty pops, direct mutation, and the intended ordering.

Common mistakes

Assuming the heap list is fully sorted.
Assigning the return value of heapify() or heappush().
Popping from an empty heap without checking.
Allowing equal-priority payloads to compare unexpectedly.
Using a heap when the consumer needs all data sorted.

The practical rule is to use a heap for repeated smallest-item access, define tie behavior, and choose top-k helpers based on k relative to n. The heap property gives fast priority operations, not a promise about the order of every element.

Keep priority queues predictable

Define what happens when two tasks have the same priority, when a task is canceled, and when the queue is empty. A heap stores values, not a built-in cancellation registry, so applications commonly add a status flag or an entry-finder layer for mutable task queues.

Do not mutate arbitrary heap entries in place and assume the invariant repairs itself. Change priorities by pushing a new entry or rebuilding the heap according to the queue design. A stale entry can be skipped when it is removed if the task has already been superseded.

For a max-priority queue with complex records, a wrapper that reverses comparisons may be clearer than negating a field. Keep comparison logic separate from payload data so serialization and debugging remain understandable.

Use an ordinary sorted list when the queue is built once and consumed in order. Use heapq when items arrive over time or the smallest item must be removed repeatedly. Choosing from the access pattern keeps the implementation simple and avoids maintaining a data structure that provides no benefit.

Document whether the priority value is lower-is-earlier or higher-is-earlier. Inverting numeric priorities for a max queue is simple, but an explicit convention prevents callers from scheduling the wrong task when the queue crosses an API boundary.

Inspect a heap through heappop() or sorted() when debugging rather than assuming the internal array is a readable priority order. The invariant, not the visual arrangement, is what makes the queue correct.

Use tuples or a wrapper with a stable comparison rule when payloads are not naturally orderable.

For priority and maximum-value workflows, compare heapq with a max-heap and list index selection. Read max heap python and python list max index for the related workflow.