Heaps and top-k operational summaries

Choose the ranking before the structure

The most frequent error is not necessarily the most urgent incident. First decide whether you are ranking counts, latency samples, or an explicit severity score. Decide how to break ties. A priority queue provides ordering; it does not supply the operational meaning of that order.

A min-heap places its smallest item at the root. To retain the largest k scores, keep the smallest retained score at that root and replace it only when a better candidate arrives. The rest of the heap is not globally sorted.

Rank a finite count table

Save as topk.py. Counts must be nonnegative integers and names must be nonempty strings. For equal counts this exercise puts the lexicographically larger name first; a different policy is valid if documented consistently.

import heapq


def top_k_counts(counts, k):
    if type(k) is not int or k < 0:
        raise ValueError("k must be a nonnegative integer")
    heap = []
    for name, count in counts.items():
        if not isinstance(name, str) or not name:
            raise ValueError("Invalid name")
        if type(count) is not int or count < 0:
            raise ValueError("Invalid count")
        if k == 0:
            continue
        candidate = (count, name)
        if len(heap) < k:
            heapq.heappush(heap, candidate)
        elif candidate > heap[0]:
            heapq.heapreplace(heap, candidate)
    return [(name, count) for count, name in sorted(heap, reverse=True)]


assert top_k_counts({"timeout": 5, "connection": 2, "retry": 5}, 2) == [
    ("timeout", 5), ("retry", 5),
]
assert top_k_counts({}, 4) == []
assert top_k_counts({"timeout": 5}, 0) == []

Let u be the number of distinct names and h = min(k, u). For k >= 1, selection costs O(u log(h + 1)), followed by O(h log(h + 1)) for ordered output; the heap takes O(h) extra space. Validation for k = 0 still scans the table.

If the counts came from n log records, their map already requires O(u) space and expected O(n) counting work. Even with a size-k heap, exact frequency counting still needs space for the full count map. When k is close to u, a full sort may be simpler and faster in practice. Measure both approaches with inputs that represent your task.

Watch the weakest retained candidate

For k=2, consider scores 2, 5, and 3. The first two fill the heap, whose root is 2. Since 3 beats 2, replacement leaves the retained scores 3 and 5. Sorting those retained items at the end gives 5, 3. The heap itself need not store every element in ranking order.

Run python3 topk.py. For the existing equal counts, (5, 'timeout') ranks above (5, 'retry') under Python tuple/string ordering, which explains the documented output. Try a full-sort comparison before changing the tie rule. If k exceeds the number of distinct names, all names are returned; negative counts and booleans are rejected because this function requires actual nonnegative integer counts.

Checkpoint and revision

Test ties, k = 1, k > u, negative counts, and boolean values. Compare against a full-sort oracle using the same tie policy. Explain how you would handle continuously changing scores; this snapshot function is not a streaming scheduler.

Checkpoint answer: a bounded selection heap does not bound the preceding exact frequency map. For changing scores, stale heap entries or updates need additional bookkeeping; this snapshot function does neither. Continue to binary search, where the useful prerequisite is sorted input rather than a heap.

Sources

Python heapq↗ and MIT binary heaps↗. The example uses the longstanding min-heap API; Python 3.14 also provides explicit max-heap operations.