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 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 time (where 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.