Exercise 2 solution

    import heapq
    import random

    class TopK:
        def __init__(self, k):
            self.k = k
            self.heap = []                       # min-heap of the k best so far

        def add(self, score, name):
            item = (score, name)
            if len(self.heap) < self.k:
                heapq.heappush(self.heap, item)
            elif item > self.heap[0]:
                heapq.heapreplace(self.heap, item)

        def best(self):
            return sorted(self.heap, reverse=True)

    t = TopK(3)
    for score, name in [(50, "ann"), (80, "bob"), (65, "cy"), (90, "di"), (40, "ed"), (80, "al")]:
        t.add(score, name)
    print(t.best())

    random.seed(7)
    scores = [(random.randint(0, 1000), "p%d" % i) for i in range(5000)]
    t = TopK(5)
    for s in scores:
        t.add(*s)
    print(t.best() == sorted(scores, reverse=True)[:5])
    print(t.best() == heapq.nlargest(5, scores))
    print(len(t.heap))

Output:
    [(90, 'di'), (80, 'bob'), (80, 'al')]
    True
    True
    5

The heap holds only the k best items seen so far, and its smallest item sits
at index 0. A new item either beats that smallest one (heapreplace swaps it in
for the cost of one heap step) or is ignored. So memory stays at k items and
each of n arrivals costs at most O(log k), instead of keeping and sorting all
n. Tuples compare score first, then name, so ties are broken the same way
sorted() and heapq.nlargest() break them, which is why all three agree.