Min Heap in Python With heapq: Operations and Examples

Quick answer: Python’s heapq module implements a min heap using a normal list. heapify transforms a list in place, heappush adds an item, and heappop removes the smallest item. The list satisfies a heap invariant, not full sorted order.

Python Pool infographic showing Python heapq maintaining the smallest root while values are pushed and popped — heapq keeps the smallest item at index zero while allowing efficient insertion and removal for priority-queue workloads.

A min heap is a tree-like structure where the smallest item is always at the root. In Python, the standard-library heapq module implements min heaps using ordinary lists.

The main references are Python’s heapq documentation, queue.PriorityQueue, and itertools.count().

With heapq, the smallest item is always available at heap[0]. Pushing and popping keep the heap invariant true, so the next smallest item can be found efficiently.

A heap is not a fully sorted list. It only guarantees that the smallest item is at index 0 and that parent-child ordering rules are maintained inside the list.

Use a heap when you repeatedly need the next smallest item and do not want to sort the whole collection after every insert. Common examples include schedulers, priority queues, graph algorithms, streaming top-k calculations, and merge operations.

The main operations are efficient: pushing and popping are O(log n), peeking at heap[0] is O(1), and turning an existing list into a heap with heapify() is O(n).

Heaps work best when you only need the next item, not random access to every item in sorted order. If your code frequently searches, deletes arbitrary entries, or updates priorities, add an index structure or choose a different data structure.

Contents

Create A Min Heap

Start with an empty list and push values into it.

import heapq

heap = []

heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)

print(heap)
print(heap[0])

The printed list may not look sorted, but heap[0] is the smallest item.

Use heappush() whenever adding an item to an existing heap. Appending directly can break the invariant.

If you need a sorted list at the end, pop items repeatedly or call sorted(heap). Do not expect the internal heap list to be sorted just because the smallest item is first.

Pop The Smallest Item

heappop() removes and returns the smallest item.

import heapq

heap = [1, 4, 7, 10, 12]

smallest = heapq.heappop(heap)

print(smallest)
print(heap)

After the pop, heapq rearranges the list so the next smallest item moves to the root.

If the heap is empty, heappop() raises IndexError. Check the heap first when empty input is possible.

Use heappop() when removal is intended. Use heap[0] only when you need to inspect the smallest item without changing the heap.

Python Pool infographic showing a min heap root, parent nodes, children, and smallest priority value — Min root: A min heap root, parent nodes, children, and smallest priority value.

Heapify An Existing List

Use heapify() to transform an existing list into a heap in place.

import heapq

numbers = [9, 3, 5, 1, 8, 2]

heapq.heapify(numbers)

print(numbers)
print(heapq.heappop(numbers))

heapify() runs in linear time, so it is the right choice when you already have all the starting items.

Do not call heapify() after every push. Push operations already maintain the heap.

When loading a large starting dataset, build a list first and call heapify() once. That is usually faster than pushing every starting item one by one.

Peek Without Removing

To peek at the smallest item, read heap[0].

def peek_min(heap):
    if not heap:
        return None
    return heap[0]

heap = [2, 6, 5, 9]

print(peek_min(heap))
print(heap)

Peeking does not modify the heap. Popping does.

Use a helper like this when empty heaps are valid in your program and you prefer None over an exception.

If None could also be a real heap item, return a custom sentinel object or raise an exception instead. The empty-heap policy should be unambiguous.

Build A Priority Queue

Store tuples when each item has a priority. The smallest tuple comes out first.

import heapq
import itertools

counter = itertools.count()
queue = []

heapq.heappush(queue, (2, next(counter), "write tests"))
heapq.heappush(queue, (1, next(counter), "fix bug"))
heapq.heappush(queue, (1, next(counter), "review patch"))

print(heapq.heappop(queue))
print(heapq.heappop(queue))

The counter breaks ties so tasks with the same priority come out in the order they were added.

This also avoids comparing task objects directly when priorities are equal.

Tuple priority queues compare items from left to right. Put the priority first, then a tie breaker, then the payload. That keeps equal-priority entries stable and avoids errors from comparing payload objects.

Python Pool infographic mapping heapq heapify, heappush, heappop, and the smallest item — heapq operations: Heapq heapify, heappush, heappop, and the smallest item.

Keep A Fixed-Size Heap

heappushpop() is useful when keeping only a limited number of items.

import heapq

top_scores = [72, 85, 90]
heapq.heapify(top_scores)

for score in [88, 91, 70, 95]:
    heapq.heappushpop(top_scores, score)

print(sorted(top_scores, reverse=True))

This keeps the three largest scores by using a min heap of size three. The smallest kept score stays at top_scores[0], so lower incoming scores are discarded efficiently.

The practical rule is: use heapq when you repeatedly need the smallest item, use heapify() for existing lists, use heap[0] for peek, and use tuple entries for priority queues. heapq is a min-heap by default; Max Heap in Python: Implementation Guide shows the mirrored max-heap invariant, implementations, and modern max-heap helpers.

For occasional sorting, use sorted(). For repeated next-smallest access, use a heap. Choosing between those two tools is mostly about how often new items arrive and how often the next item is needed.

Keep heap code small and disciplined: only mutate the list through heapq operations, document the tuple shape for priority queues, and test empty-heap behavior explicitly.

Understand The Invariant

For every parent position, the parent is less than or equal to its children. That guarantees the smallest value at index zero without requiring every other pair to be sorted.

Python Pool infographic comparing heap entries, tuple priorities, tasks, and stable tie breakers — Priority queue: Heap entries, tuple priorities, tasks, and stable tie breakers.

Build Efficiently

Use heapq.heapify(values) when starting with an existing list. It rearranges the list in linear time and avoids repeatedly pushing every item into a new heap.

Use Push And Pop

heappush maintains the invariant after adding an item, while heappop returns the smallest item and restores the invariant. Do not call pop(0), which has different complexity and semantics.

Create Priority Queues

Store tuples such as (priority, sequence, task) when ties need deterministic ordering. Ensure every tuple position used for comparison is mutually comparable, or provide a comparable wrapper.

Python Pool infographic testing empty heaps, duplicates, mutations, and heap invariants — Heap checks: Empty heaps, duplicates, mutations, and heap invariants.

Inspect Without Sorting

values[0] is the smallest item when the heap is non-empty, but the rest of the list is not sorted. Copy and use sorted only for display or reporting when full order is actually required.

Test Empty And Ties

Test an empty heap, duplicate priorities, negative values, tuples, and a sequence of pushes and pops. Confirm that the popped sequence is non-decreasing and that the original input mutation is understood.

The official heapq documentation defines the min-heap operations. Related Python Pool references include lists and tests.

For related ordering patterns, compare shortest-path queues, list behavior, and invariant tests when using a min heap.