Course contentsShow
← Python
Lesson 259 of 1,0604. Data Structures MasteryFree lesson

Optimizing Selection with Heap Invariants

Master the maintenance of heap invariants to extract the top N largest or smallest items from large datasets without performing full sorts.

In this lesson, you will learn how to extract the "Top N" items from a massive dataset efficiently by maintaining the heap invariant instead of sorting the entire collection.

Beyond Full Sorting

When you need the 5 largest values from a list of a million numbers, sorting the entire list takes O(Nlog⁡N)O(N \log N) time. This is wasteful because you only care about a tiny fraction of the data. Instead, we can use the heap invariant—a property where the parent node is always smaller (or larger) than its children—to keep track of only the elements we need.

The Strategy: Bounded Heaps

By maintaining a heap of exactly N elements, we can process a stream of data in O(Mlog⁡N)O(M \log N) time (where MM is the size of your dataset). If you want the "Top 5" largest items, you maintain a min-heap of size 5. As you iterate through the dataset, if a new number is larger than the smallest item in your heap (the root), you remove that root and insert the new number. Because the heap invariant is restored automatically, the "smallest" of your top candidates is always instantly accessible at the root.

Here is how you implement this with Python’s heapq:

import heapq

data = [50, 1, 99, 12, 45, 87, 2, 66]
top_n = []

for val in data:
    if len(top_n) < 3:
        heapq.heappush(top_n, val)
    elif val > top_n[0]:
        heapq.heapreplace(top_n, val)

# top_n now contains the 3 largest values
print(top_n) # Output: [66, 87, 99]

Why this scales

The heapreplace operation is highly efficient; it pops the root and pushes a new item while maintaining the heap invariant in a single, optimized step. By keeping the heap size constrained to N, you minimize memory overhead and keep the logarithmic cost tied to your desired output size rather than the massive input size. This turns a massive sorting problem into a simple, maintainable process of filtering.

Key Takeaway: Maintaining a bounded heap allows you to extract top-ranking items in logarithmic time relative to the number of items sought, avoiding the heavy cost of sorting an entire dataset.