Python heapq top-k: define ties before ranking frequencies

Operation contract

The receipt-category fixture counts events, then asks nlargest for the two most frequent categories. The ranking key includes the category name as a tie-breaker, choosing reverse alphabetical order when counts match. Defining that policy prevents a test from accidentally relying on input dictionary order for equal frequencies.

Failure and ownership boundary

Counting retains every distinct category before top-k selection, so a small k does not bound the entire pipeline’s memory. User-controlled category names also need length/count limits in a service. Python sets: membership and deduplication do not preserve input order explains why a set cannot replace Counter, and Java heaps: keep the largest k values with a small priority queue covers the related Java operation.

Working program

from collections import Counter
from heapq import nlargest

categories = ["accepted", "rejected", "accepted", "queued", "rejected", "accepted"]
counts = Counter(categories)
ranked = nlargest(2, counts.items(), key=lambda item: (item[1], item[0]))
print(ranked)

Output

[('accepted', 3), ('rejected', 2)]

Costs and limits

Counting n events uses O(n) expected hash work and O(u) retained counts for u distinct categories. Selection commonly uses O(u log k) comparison work when k is small; sorting fallback/large-k behavior and string comparisons affect the exact implementation cost.

Common Mistakes

• Declare a tie-breaker instead of relying on incidental order.
• Small k does not limit the frequency map.

Connected lessons

Python dictionaries: insertion order and duplicate-key replacement, Python sets: membership and deduplication do not preserve input order, Java heaps: keep the largest k values with a small priority queue.

Apply this boundary

Python Counter and deque: counts, queues and bounded history, Python Dijkstra: nonnegative weights and stale heap entries.

Trace the next boundary

Python exercise: select the highest scores with stable tie order.

Follow the integrity boundary

Python running median: two heaps with an exact even-count result.