PYTHON
Find N Largest or Smallest Items Efficiently with `heapq`
Learn to quickly retrieve the N largest or smallest elements from a collection without a full sort, using Python's `heapq` module for optimal performance.
import heapq
data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
# Find the 3 largest items
largest_three = heapq.nlargest(3, data)
# Expected: [9, 8, 7]
# Find the 4 smallest items
smallest_four = heapq.nsmallest(4, data)
# Expected: [0, 1, 2, 3]
# Example with objects (dictionaries) and a key function
portfolio = [
{'name': 'AAPL', 'price': 150.00, 'shares': 10},
{'name': 'GOOG', 'price': 2500.00, 'shares': 2},
{'name': 'MSFT', 'price': 300.00, 'shares': 5},
{'name': 'AMZN', 'price': 3000.00, 'shares': 1},
{'name': 'TSLA', 'price': 800.00, 'shares': 3},
]
# Find the 2 stocks with the highest price
highest_price_stocks = heapq.nlargest(2, portfolio, key=lambda s: s['price'])
# Expected: [{'name': 'AMZN', 'price': 3000.00, 'shares': 1}, {'name': 'GOOG', 'price': 2500.00, 'shares': 2}]
# Find the 2 stocks with the lowest number of shares
lowest_share_stocks = heapq.nsmallest(2, portfolio, key=lambda s: s['shares'])
# Expected: [{'name': 'AMZN', 'price': 3000.00, 'shares': 1}, {'name': 'GOOG', 'price': 2500.00, 'shares': 2}]
How it works: The `heapq` module implements the heap queue algorithm, also known as the priority queue algorithm. `heapq.nlargest()` and `heapq.nsmallest()` efficiently find the N largest or smallest elements from an iterable, respectively, without fully sorting the entire collection. This is significantly more efficient than a full sort when only a few extreme values are needed and works with complex objects using a `key` function.