Top K Elements — How the Pattern Works
The Top K Elements pattern uses a binary heap (priority queue) to select the k largest, smallest, or most frequent items—or to repeatedly extract and update a dynamic extremum—without fully sorting the input. When tracking the k largest elements, a min-heap bounded at capacity k maintains the invariant that heap[0] holds the smallest (weakest) of the k best candidates seen so far, allowing incoming values <= heap[0] to be discarded in O(1) time and replacements to execute in O(log k) time (symmetrically, a max-heap of size k tracks the k smallest elements). This eliminates redundant ordering among discarded elements, reducing full-sort O(n log n) passes to O(n log k) time and O(k) space, and accelerating k repeated extremum updates from O(n * k) linear scans to O(n + k log n).
- The prompt asks for the k largest, k smallest, k closest, or kth ranked element in a static array or an unbounded data stream.
- You need the k most or least frequent elements after counting occurrences in a hash map, or must greedily interleave high-frequency items subject to an adjacency cooldown.
- An objective combines an additive term and a bottleneck term—such as (sum of k values) * (minimum efficiency) or (max wage-to-quality ratio) * (sum of k qualities)—allowing you to sort by the bottleneck and maintain a size-k heap over the sum.
- A greedy simulation repeatedly extracts the current global minimum or maximum, mutates it (e.g., ceiling division, increment, or multiplication), and reinserts it across k operations.
- You need the top k or kth best value from an implicitly ordered combinatorial space (e.g., O(n^2) pair sums, O(2^n) subsequence sums, or k sorted lists) where each popped state expands O(1) immediate frontier neighbors.
- Inverting heap polarity: using a max-heap of size k to find the k largest elements evicts the largest values and retains the k smallest; always pair k largest with a min-heap and k smallest with a max-heap.
- Tuple comparison crashes or reversed tie-breakers in heapq: Python compares tuples left-to-right, so when negating keys (-priority, idx, item), verify that tie-breaker fields are comparable and have the intended sign (e.g., positive idx to prefer smaller indices on ties).
- Missing deduplication for distinct ranks or shared frontier neighbors: distinct-rank queries (such as Third Maximum Number) and 2D index expansions ((i + 1, j) vs. (i, j + 1)) push duplicate entries unless guarded by a synchronized hash set.
- Desynchronized auxiliary state on eviction: when tracking a running sum or membership set alongside a bounded heap, every heappop/heapreplace must update the sum (accounting for negated values) or remove the evicted key from the set.
- Applying modular arithmetic before comparison: in optimization problems like Maximum Performance of a Team or Maximum Product After K Increments, track exact values (or heap ordering) during the algorithm and take modulo 10^9 + 7 only when computing the final return value.
import heapq
def top_k_largest(nums, k):
heap = []
for num in nums:
if len(heap) < k:
heapq.heappush(heap, num)
elif num > heap[0]:
heapq.heapreplace(heap, num)
return heap # heap[0] is the kth largestimport heapq
def top_k_smallest(items, k, key_fn):
heap = []
for item in items:
key = key_fn(item)
heapq.heappush(heap, (-key, item))
if len(heap) > k:
heapq.heappop(heap)
return [item for _, item in heap]import heapq
def apply_k_updates(nums, k, transform):
heap = [(num, i) for i, num in enumerate(nums)]
heapq.heapify(heap)
for _ in range(k):
val, idx = heapq.heappop(heap)
nums[idx] = transform(val)
heapq.heappush(heap, (nums[idx], idx))
return numsimport heapq
def k_best_pair_sums(a, b, k):
heap = [(-(a[0] + b[0]), 0, 0)]
seen, result = {(0, 0)}, []
while len(result) < k:
neg_sum, i, j = heapq.heappop(heap)
result.append(-neg_sum)
for ni, nj in ((i + 1, j), (i, j + 1)):
if ni < len(a) and nj < len(b) and (ni, nj) not in seen:
seen.add((ni, nj))
heapq.heappush(heap, (-(a[ni] + b[nj]), ni, nj))
return result