Pattern 11 of 27

Heap and Top K

Use a priority queue to keep only the k best items seen so far, or to always process the smallest or largest item next.

Cost: O(n log k) time, O(k) space
Problems: 6

When to reach for it

The prompt says k largest, k smallest, k closest, or k most frequent.
Items arrive over time and you need the current best at every step.
Sorting everything does more work than the question needs.

How it works

To keep the k largest items, hold a min-heap of size k. Each new item goes in, and if the heap grows past k the smallest is removed, so the heap always holds the top k and its root is the kth largest. That costs O(n log k) instead of sorting all n. The same structure models simulations that repeatedly take the biggest or smallest element, such as smashing the two heaviest stones together.

The template

Written for Kth Largest Element in an Array (write-up)

import heapq

def find_kth_largest(nums, k):
    heap = []                         # min-heap of the k largest so far
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

Open in the editor Trace it line by line

Six problems, in learning order

What usually goes wrong

Pushing all n items into a max-heap when a size-k min-heap is enough.
Python's heapq is only a min-heap; negate values to get max-heap behaviour.
Tie-breaking rules, like alphabetical order in Top K Frequent Words, reverse the heap comparison.

Heap and Top K, answered

When should I use the heap and top k pattern?

The prompt says k largest, k smallest, k closest, or k most frequent. Items arrive over time and you need the current best at every step. Sorting everything does more work than the question needs.

What is the time complexity of heap and top k?

O(n log k) time, O(k) space. The same structure models simulations that repeatedly take the biggest or smallest element, such as smashing the two heaviest stones together.

Which problem should I start with for heap and top k?

Start with Kth Largest Element in an Array (LeetCode 215, Medium). A size-k min-heap whose root is the answer. The six problems on this page are in learning order.