Heaps and Top-K

Updated Nov 19, 2026 · 4 min read
On this page

    A heap gives you the smallest (or largest) item in O(1) and lets you add or remove items in O(log n). That makes it the tool for "best so far" questions: the k largest values, the k closest points, the next event in time order, the median of a stream. You never sort everything, you only keep what can still matter.

    Heaps covers how a heap works. Python's heapq is a min-heap; for a max-heap, push negated values.

    When to recognise it

    • "k largest / k smallest / k most frequent / k closest": a heap of size k.
    • "Merge k sorted lists / arrays / streams": a heap holding the current head of each.
    • "Median of a data stream", "sliding median": two heaps.
    • Scheduling: "which task, room or machine frees up next?" A heap of end times (see Intervals).
    • Shortest paths with weights (Dijkstra): a heap of (distance, node). See Graph BFS and DFS.

    Pattern 1: top-k with a size-k heap

    To find the k largest, keep a min-heap of size k. Its root is the smallest of the k biggest values seen so far, so anything smaller than the root cannot be in the top k. When the heap grows past k, pop the root.

    Reading [3, 2, 1, 5, 6, 4] with k = 3. The heap fills to [1, 2, 3], then each new value pushes out the smallest: 1, then 2, then 3. The final root 4 is the 3rd largest.
    Reading [3, 2, 1, 5, 6, 4] with k = 3. The heap fills to [1, 2, 3], then each new value pushes out the smallest: 1, then 2, then 3. The final root 4 is the 3rd largest.
    import heapq
    
    def kth_largest(nums, k):
        """Min-heap of size k: the root is the smallest of the k biggest, i.e. the k-th largest."""
        heap = []
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k:
                heapq.heappop(heap)          # throw away the smallest
        return heap[0]

    Time O(n log k), space O(k). That beats sorting (O(n log n)) when k is small, and it works on a stream you cannot store.

    For "top k frequent", count first and push (count, value) pairs:

    import heapq
    from collections import Counter
    
    def top_k_frequent(nums, k):
        """Same idea with (count, value) pairs. Ties broken by value so the output is deterministic."""
        heap = []
        for val, cnt in Counter(nums).items():
            heapq.heappush(heap, (cnt, -val))
            if len(heap) > k:
                heapq.heappop(heap)
        return sorted((-v for c, v in heap))

    Pattern 2: k-way merge

    Each list is sorted, so the overall smallest item is one of the k current heads. Keep those heads in a heap, pop the smallest, and push the next item from the same list.

    import heapq
    
    def merge_k_sorted(lists):
        """K-way merge: the heap holds the current head of every list."""
        heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
        heapq.heapify(heap)
        out = []
        while heap:
            val, i, j = heapq.heappop(heap)
            out.append(val)
            if j + 1 < len(lists[i]):
                heapq.heappush(heap, (lists[i][j + 1], i, j + 1))   # i breaks ties
        return out

    Time O(N log k) for N total items. The list index i in the tuple breaks ties, so Python never has to compare two list nodes or objects.

    Pattern 3: two heaps for a running median

    Split the numbers into a low half (a max-heap) and a high half (a min-heap). The median sits at the tops.

    Low half 1, 2, 5 in a max-heap with 5 on top; high half 7, 9 in a min-heap with 7 on top. With an odd count the low half has one extra, so the median is 5.
    Low half 1, 2, 5 in a max-heap with 5 on top; high half 7, 9 in a min-heap with 7 on top. With an odd count the low half has one extra, so the median is 5.
    import heapq
    
    class RunningMedian:
        """Two heaps: max-heap for the low half (stored negated), min-heap for the high half."""
        def __init__(self):
            self.low, self.high = [], []
    
        def add(self, x):
            heapq.heappush(self.low, -x)
            heapq.heappush(self.high, -heapq.heappop(self.low))   # keep every low <= every high
            if len(self.high) > len(self.low):
                heapq.heappush(self.low, -heapq.heappop(self.high))
    
        def median(self):
            if len(self.low) > len(self.high):
                return -self.low[0]
            return (-self.low[0] + self.high[0]) / 2

    Common bugs

    • Using a max-heap for "k largest": you would keep everything. Keep a min-heap of size k and drop from the bottom.
    • Forgetting that heapq is a min-heap and getting the order backwards. Negate for a max-heap.
    • Ties in tuples: (priority, node) crashes in Python 3 when two priorities are equal and nodes can't be compared. Add a counter or index as the second field.
    • Building the heap with repeated pushes when you have all items: heapify is O(n).
    • Returning heap as if it were sorted. A heap list is only partly ordered; sort it if the order matters.

    Say this in the interview

    • "I keep a min-heap of the k largest so far. The root is the weakest of them, so each new value either beats it and replaces it, or is ignored. O(n log k) time, O(k) space."
    • "If k is close to n, quickselect is O(n) on average, but the heap also works on a stream."

    Problems for this pattern

    1. Last Stone Weight: a max-heap, smash the two largest.
    2. Kth Largest Element in an Array: the size-k heap.
    3. Top K Frequent Elements: count, then a heap.
    4. K Closest Points to Origin: a max-heap of size k by distance.
    5. Task Scheduler: a max-heap of remaining counts.
    6. Merge k Sorted Lists: k-way merge.
    7. Find Median from Data Stream: two heaps.
    8. Sliding Window Median: two heaps with lazy deletion as the window moves.

    Related

    Heaps · Intervals (rooms as a heap of end times) · Graph BFS and DFS (Dijkstra) · Greedy