Top K Without a Heap

The Idea

A heap gives you the top k in O(n log k). But a count can never be larger than the array itself, so counts make perfectly good array indices: buckets[c] holds every value seen exactly c times. Tally with a map, drop each value into its count bucket, then walk the buckets downwards and take until you have k. Linear, and nothing is compared with anything.

Real-World Example

A newsroom dashboard ranking today's most-read articles. Each article's hit count is a shelf number, not a sort key; the editor reads shelves from the top down and stops as soon as the front page is full.

The Code

def top_k(nums, k):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
    buckets = [[] for _ in range(len(nums) + 1)]   # index = how often
    for value, c in counts.items():
        buckets[c].append(value)
    out = []
    for c in range(len(nums), 0, -1):              # walk down from the top
        out += buckets[c]
        if len(out) >= k:
            return out[:k]
    return out

print(top_k([1, 1, 1, 2, 2, 3], 2))   # [1, 2]