# Title: Top k items with a heap
# Heading: Python Program to Find the K Largest Elements Using a Heap
# Level: intermediate
# Tags: k largest elements, top k, heap, heapq, priority queue
# Time: O(n log k)
# Space: O(k)
# About: Finds the k largest items in a list with heapq, keeping a min-heap of the k biggest seen so far, so the list never has to be sorted.

import heapq


def top_k(items, k):
    """The k largest items, largest first."""
    heap = []  # min-heap: heap[0] is the smallest kept
    for item in items:
        if len(heap) < k:
            heapq.heappush(heap, item)
        elif item > heap[0]:
            # Swap the smallest kept for this bigger item
            heapq.heapreplace(heap, item)
    return sorted(heap, reverse=True)


scores = [42, 17, 93, 8, 61, 75, 29, 88, 54]
print("Top 3 scores:", top_k(scores, 3))