Top-K with Heaps

    DSA · Intermediate

    Definition

    Keep a min-heap of size k; its top is the k-th largest element.

    Efficient for top-k frequent, k closest points and streams.

    Diagram

    heap(k=2): [5, 6]k-th largest = 5

    Flowchart

    Push elementIf size > k, pop smallestTop is k-th largest

    Example: K-th largest

    import heapq
h = []
for x in [3, 2, 1, 5, 6, 4]:
    heapq.heappush(h, x)
    if len(h) > 2: heapq.heappop(h)
print(h[0])

    Output: 5

    Complexity

    O(n log k)

    Key points

    • heapq is a min-heap; negate for max-heap
    • heapq.nlargest is a shortcut

    Interview questions

    Why size-k heap instead of sorting?

    O(n log k) beats O(n log n) when k is small.

    More DSA topics

    ArraysLinked ListStackQueue