Offensive Security Researcher & Quantum Cryptography Analyst

heapq Largest and Smallest Items in a Collection in Python: Complete Heap Queue Algorithm Implementation Guide

Abdul Wahab Junaid
heapq Largest and smallest items in a collection in python

heapq Largest and smallest items in a collection in python

Whenever I need to find the top N or bottom N items in a large collection efficiently, my mind goes straight to Python’s heapq module. Sorting an entire list just to grab the top 3 elements always felt wasteful to me once I understood how heaps work — and once I actually learned heapq.nlargest() and heapq.nsmallest(), it changed how I approach a whole category of problems involving priority, ranking, and streaming data.

What Is a Heap, Really?

A heap is a specialized tree-based data structure that satisfies the heap property: in a min-heap, every parent node is smaller than or equal to its children; in a max-heap, every parent is greater than or equal to its children. Python’s heapq module implements a binary min-heap using a plain list, where for any index i, the children are located at 2*i + 1 and 2*i + 2.

This structure guarantees that the smallest element is always at index 0, which means I can access the minimum in O(1) time, and pushing or popping an item takes O(log n) time because the heap only needs to “bubble” the element up or down the tree — it never needs to fully re-sort the collection.

Getting Started with heapq

import heapq

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

Output:

[1, 3, 2, 5, 7, 9]

Notice this isn’t a fully sorted list — it’s just structured so that numbers[0] is guaranteed to be the smallest element. That’s the whole point of a heap: it maintains partial order efficiently rather than paying the cost of full sorting.

Basic Push and Pop

heapq.heappush(numbers, 0)
print(numbers)

smallest = heapq.heappop(numbers)
print(smallest)
print(numbers)

Output:

[0, 1, 2, 5, 7, 9, 3]
0
[1, 3, 2, 5, 7, 9]

Finding the N Largest and N Smallest Items

This is where heapq really shines for me. Instead of manually building a heap and popping repeatedly, I can use two purpose-built functions:

import heapq

scores = [72, 88, 45, 90, 67, 99, 53, 81]

top_3 = heapq.nlargest(3, scores)
bottom_3 = heapq.nsmallest(3, scores)

print("Top 3:", top_3)
print("Bottom 3:", bottom_3)

Output:

Top 3: [99, 90, 88]
Bottom 3: [45, 53, 67]

Using a key Function

Both nlargest() and nsmallest() accept a key parameter, which I find invaluable when working with lists of dictionaries or objects rather than plain numbers.

students = [
    {"name": "Ayesha", "score": 88},
    {"name": "Bilal", "score": 95},
    {"name": "Sana", "score": 72},
    {"name": "Hamza", "score": 91},
]

top_2 = heapq.nlargest(2, students, key=lambda s: s["score"])
print(top_2)

Output:

[{'name': 'Bilal', 'score': 95}, {'name': 'Hamza', 'score': 91}]

This pattern comes up constantly in my own scripts — ranking products by price, finding the slowest API calls in a log, or picking the top few candidates from survey results.

Why Not Just Sort the List?

I get asked this a lot: “Why not just do sorted(list)[:3]?” The answer comes down to algorithmic complexity.

When k is small relative to n (say, I want the top 5 out of a million records), nlargest/nsmallest is significantly faster because the heap it maintains internally never grows beyond size k. Under the hood, heapq.nlargest iterates through the collection, maintaining a min-heap of size k — if a new element is bigger than the smallest item in the heap, it replaces it; otherwise, it’s discarded. That’s why the complexity depends on k, not on sorting everything.

Here’s roughly what that looks like internally (simplified):

def my_nlargest(k, iterable):
    heap = []
    for item in iterable:
        if len(heap) < k:
            heapq.heappush(heap, item)
        elif item > heap[0]:
            heapq.heapreplace(heap, item)
    return sorted(heap, reverse=True)

heapq.heapreplace() is more efficient than a separate pop followed by a push because it does both in a single sift operation.

Memory and Performance Characteristics

Because a heap is stored as a flat Python list, its memory footprint is essentially the same as a regular list of the same length — there’s no extra pointer overhead like there would be with a linked tree structure. This is one of the reasons Python’s heap implementation is fast in practice: it benefits from cache-friendly, contiguous memory access.

For nlargest(k, iterable) and nsmallest(k, iterable), memory usage is bounded by O(k) for the heap itself, plus whatever it costs to iterate the original iterable — which means I can even use these functions on generators without materializing the whole sequence in memory first.

def read_large_file(path):
    with open(path) as f:
        for line in f:
            yield int(line.strip())

top_5 = heapq.nlargest(5, read_large_file("numbers.txt"))
print(top_5)

This lazy evaluation is genuinely useful when processing huge log files or streaming data where loading everything into a list isn’t practical.

Practical, Real-World Use Cases

I’ve used heapq‘s largest/smallest functions in scenarios like:

import heapq

tasks = [(3, "Write report"), (1, "Fix critical bug"), (2, "Reply to email")]
heapq.heapify(tasks)

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

Output:

Processing: Fix critical bug (priority 1)
Processing: Reply to email (priority 2)
Processing: Write report (priority 3)

Common Mistakes and Debugging Tips

  1. Assuming the heap list is fully sorted. Only heap[0] is guaranteed to be the smallest — the rest of the list is not in sorted order.
  2. Comparing incompatible types. If I try to heapify a list of tuples where the first elements are equal, Python falls back to comparing the second elements — and if those aren’t comparable (like mixing dicts), it raises a TypeError. I avoid this by adding a unique tiebreaker, like an index.
import heapq
import itertools

counter = itertools.count()
tasks = []
heapq.heappush(tasks, (2, next(counter), "task A"))
heapq.heappush(tasks, (2, next(counter), "task B"))
  1. Using nlargest/nsmallest when k is close to n. In that case, plain sorted() is actually more efficient since the overhead of maintaining a heap isn’t worth it. As a rule of thumb, when k is a small fraction of n, heapq wins; when k approaches n, sorting wins.
  2. Forgetting heapify() before pushing/popping manually built lists. A regular list doesn’t automatically satisfy the heap property just because I intend it to — I always call heapq.heapify() first.

Best Practices I Follow

FAQs

Q: Is heapq a max-heap or a min-heap? It’s a min-heap by default. To simulate a max-heap, I negate the values before pushing them and negate them again when popping.

Q: Can I use heapq with custom objects? Yes, as long as the objects support comparison operators, or I supply a key function to nlargest/nsmallest.

Q: Is heapq thread-safe? No, heapq provides no built-in locking. If multiple threads modify the same heap, I need to protect it with a threading.Lock.

Q: What’s the time complexity of heapq.heappush() and heapq.heappop()? Both are O(log n).

Q: When should I use heapq instead of sorted()? When I only need the top or bottom K elements out of a much larger collection, or when I need an efficient priority queue with repeated insertions and removals.

Troubleshooting Tips

Summary

The heapq module gave me an efficient, low-overhead way to solve a whole class of “top K” and priority-based problems without paying the cost of sorting an entire collection. Once I understood that a heap only maintains partial order — with the smallest element always accessible at index 0 — everything about nlargest(), nsmallest(), and priority queues clicked into place.

References

Exit mobile version