Heaps for Top-k

heapq and the size-k heap

Python's heapq is a min-heap with O(log n) push and pop. For the k largest items, keep a min-heap of size k and pop whenever it grows past k: the root is then the k-th largest, in O(n log k) time and O(k) space. heapq.nsmallest and nlargest with a key handle top-k with ties (such as frequency then alphabetical order). Heaps also merge k sorted lists and schedule tasks.

Best-first and sort-first

Heaps keep the best few items, sorting tames intervals, and greedy choices work when local best is globally best.

Top-k frequent words and the k-th largest, run

I ran this with Python 3.12.3 (standard library only). "the" appears 4 times and "is" 3 times, then "sunny"; the 2nd largest of the first list is 5 and the 4th largest of the second is 4.

# Heaps: top-k frequent words and the k-th largest number
import heapq
from collections import Counter

def top_k_frequent(words, k):
    counts = Counter(words)
    return heapq.nsmallest(k, counts, key=lambda w: (-counts[w], w))

def kth_largest(nums, k):
    heap = []                             # min-heap of the k largest so far
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

words = "the day is sunny the the the sunny is is".split()
print(top_k_frequent(words, 3))
print(kth_largest([3, 2, 1, 5, 6, 4], 2), kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))

Output:

['the', 'is', 'sunny']
5 4

Negate for a max-heap

heapq has no max-heap; push negative values or tuples with negated keys.

त्वरित जाँच: What does a min-heap of size k contain after scanning an array for the k largest?

• The k smallest elements
• The k largest elements, with the k-th largest at the root
• All elements sorted
• Only the maximum