Heaps and top-k

“Return the k most frequent words.” Sorting everything works, at O(n log n). But it does far more than asked. It puts all n items in order, when you only wanted the best k, in any order. A heap does exactly what’s asked. It keeps a collection where the smallest (or largest) item is always on top. Adding or removing one item costs O(log n).

That one guarantee covers a family of problems: “the top is the extreme, and nothing else is promised”. The k best of anything. Merging sorted streams. Always picking the cheapest next step. And keeping a running median.

What makes this hard

• A heap gives the min (or max) in O(1), and push and pop in O(log n). It is not sorted beyond the top.
• Top k largest: use a min-heap of size k. The top is the weakest of the k best, so it’s the one to evict. O(n log k) time and O(k) memory.
• Merge k sorted lists: keep a heap of one candidate per list. Pop the smallest, and push its successor. That’s O(N log k), for N items in total.
• Greedy “cheapest next”: Dijkstra, task scheduling and meeting rooms all pop the best option, act on it, and push what it unlocks.
• Two heaps split data into a lower and an upper half, so the median is always on top.

How to spot it

• “k largest”, “k smallest”, “k closest”, “k most frequent”, “kth largest”.
• A stream where you must report the best so far after each new item.
• Merging sorted things: k sorted lists, k sorted arrays, the smallest pair sums.
• Always process the most urgent or cheapest item next, while new items keep arriving: scheduling, simulations, Dijkstra’s shortest paths.
• A running median.

Watch it run

Kth largest in a stream, with k = 3. The heap holds the three largest numbers so far, smallest on top. A new number joins. If that makes four, the smallest of the four leaves. The top is always the 3rd largest overall.

stream

5183927

heap (rank = 3) top first

empty

kth largest

not yet

1. heap = [] # min-heap, k largest so far
2. for number in stream:
3. heapq.heappush(heap, number)
4. if len(heap) > rank:
5. heapq.heappop(heap) # drop the smallest
6. kth_largest = heap[0] # kth largest so far

Keep the 3 largest numbers seen so far in a min-heap. Its smallest member, the top, is the 3rd largest overall.

← BackStep →Play1 / 9

The surprising part is the direction. To keep the largest k, use a min-heap. You need fast access to the item you’d throw out, and that’s the smallest of the k. The heap is shown sorted, so it’s easy to read. A real heap only promises that the top is the smallest.

The template

Kth largest with a size-k heap, and merging sorted lists. The code calls k rank:

JHeaps.javaPyexample.pyC#Heaps.csGomin_heap.goTSheap.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Heaps {
    static int kthLargest(int[] nums, int rank) {
        // Keep the k largest values seen so far in a min-heap. Its top is the smallest of
        // them, which is the kth largest overall. When the heap grows past k, the top can't be
        // in the top k any more. O(n log k) time, O(k) memory, and it works on a stream.
        PriorityQueue<Integer> heap = new PriorityQueue<>(); // a min-heap by default
        for (int number : nums) {
            heap.add(number);
            if (heap.size() > rank) heap.poll();
        }
        return heap.peek();
    }

    static List<Integer> mergeSorted(List<List<Integer>> lists) {
        // The heap holds one candidate per list: its next unread value, as {value, list,
        // index}. The smallest candidate is the next output value, and only its own list can
        // supply the one after it. Integer.compare, not a - b, which can overflow.
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (first, second) -> Integer.compare(first[0], second[0]));
        for (int i = 0; i < lists.size(); i++) {
            if (!lists.get(i).isEmpty()) heap.add(new int[] {lists.get(i).get(0), i, 0});
        }
        List<Integer> merged = new ArrayList<>();
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            merged.add(top[0]);
            List<Integer> list = lists.get(top[1]);
            int next = top[2] + 1;
            if (next < list.size()) heap.add(new int[] {list.get(next), top[1], next});
        }
        return merged;
    }

    public static void main(String[] args) {
        check(kthLargest(new int[] {5, 1, 8, 3, 9, 2, 7}, 3) == 7);
        check(kthLargest(new int[] {3, 2, 1, 5, 6, 4}, 2) == 5);
        List<List<Integer>> lists = List.of(List.of(1, 4, 7), List.of(2, 5), List.of(), List.of(3, 6, 9));
        check(mergeSorted(lists).equals(List.of(1, 2, 3, 4, 5, 6, 7, 9)));
        System.out.println("ok: kthLargest and mergeSorted");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

The languages differ more here than anywhere else in the track:

• Python’s heapq works on a plain list and is a min-heap only. For a max-heap, push negated values. Push tuples to order by the first field, and add a tiebreaker (like an index) so equal priorities never compare the next field.
• Java’s PriorityQueue is a min-heap by default. Pass Comparator.reverseOrder() for a max-heap. Write comparators with Integer.compare, not a - b, which overflows.
• C#’s PriorityQueue<TElement, TPriority> (.NET 6 and later) takes the priority separately and is a min-heap on it.
• Go’s container/heap needs a type with five methods, which is the boilerplate in the Go tab.
• TypeScript has no heap at all. Interviewers accept “I’d use a library”, if you also say how a binary heap works. The TypeScript tab includes a short one.

Variations

Top k frequent

Count with a hash map. Then keep the k most frequent in a size-k min-heap, keyed by count. That’s O(n log k). There’s also an O(n) answer: bucket sort by frequency. Make an array where index f holds the items that appear f times. Then walk it from the highest frequency down, until you have k items. Mention both. The heap is more general. The buckets are faster here.

Two heaps for a running median

Keep the smaller half in a max-heap, and the larger half in a min-heap. Their sizes are equal, or the lower half is one bigger. A new number goes into the lower half. Then the lower half’s top moves to the upper half. Then, if the upper half is bigger, its top moves back. The median is the lower top, or the average of both tops. Each step is O(log n).

Dijkstra’s shortest paths

BFS finds shortest paths when every edge costs 1. With weights, replace the queue with a min-heap, ordered by distance so far. Pop the closest unfinished node, and finalize it. Then push its neighbors with their new distances. That’s network delay time. It needs non-negative weights.

TradeoffHeap of size k vs sorting vs quickselect

We gain

The heap is O(n log k) with O(k) memory, and it works on a stream you can only read once.

We give up

Sorting is O(n log n), but it’s the simplest to write, and gives the k in order. Quickselect finds the kth largest in O(n) on average, but O(n²) in the worst case. It needs the whole array in memory, and rearranges it. For a one-off on an array, quickselect is fastest. For a stream, or when k is small, the heap wins.

Complexity

	Time	Extra memory
Push, pop	O(log n)
Peek	O(1)
Build a heap from n items (heapify)	O(n)
Top k from n items	O(n log k)	O(k)
Merge k sorted lists of N items in total	O(N log k)	O(k)

Common mistake

Using a max-heap of everything for top k

Pushing all n items into a max-heap and popping k is O(n + k log n) with heapify, or O(n log n) with n pushes. And it holds all n items in memory. It works. But the size-k min-heap is the answer interviewers are looking for. It also works when n is too large to hold, or the data arrives as a stream.

Say this out loud

I only need the k largest, not a full sort. I’ll keep a min-heap of size k. Its top is the smallest of my current best k, so it’s the one to evict. That’s O(n log k).

Interview questions

Interviewer asksWhy a min-heap for the k largest elements?

Because the operation you need on every step is “evict the weakest of my current best k”. The weakest of the largest values is the smallest. A min-heap puts exactly that item on top. With a max-heap, you’d need to keep all n items, since you can’t tell which ones to drop.

Interviewer asksMerge k sorted lists: why is it O(N log k) and not O(N log N)?

The heap never holds more than k items, one per list, so each push and pop costs O(log k). Every one of the N items is pushed once and popped once. Merging the lists pairwise, like merge sort, also gets O(N log k). Merging them one by one into a growing result is O(N × k).

Interviewer asksTask scheduler: where does the heap come in, and is there a faster answer?

The simulation always runs the most frequent task that’s off cooldown: a max-heap by remaining count, plus a queue of tasks cooling down. That’s O(n log 26). There’s also a formula: with the highest count m shared by c tasks, the answer is max(len(tasks), (m - 1) × (n + 1) + c). Lead with the simulation, since it explains the formula.

Practice

10 problems on LeetCode: 2 easy, 6 medium, 2 hard

1. Kth Largest Element in a Stream↗(opens LeetCode in a new tab)

   A min-heap of size k keeps the answer at its top.

   Easy
2. Last Stone Weight↗(opens LeetCode in a new tab)

   A max-heap hands you the two heaviest each round.

   Easy
3. Kth Largest Element in an Array↗(opens LeetCode in a new tab)

   Size-k min-heap, or quickselect for average O(n).

   Medium
4. Top K Frequent Elements↗(opens LeetCode in a new tab)

   Count with a map, then keep the k most frequent in a heap.

   Medium
5. K Closest Points to Origin↗(opens LeetCode in a new tab)

   A max-heap of size k evicts the farthest point so far.

   Medium
6. Task Scheduler↗(opens LeetCode in a new tab)

   Always run the most frequent task that is off cooldown.

   Medium
7. Reorganize String↗(opens LeetCode in a new tab)

   Place the most frequent letter, then hold it back one turn.

   Medium
8. Network Delay Time↗(opens LeetCode in a new tab)

   Dijkstra: a min-heap always expands the closest node next.

   Medium
9. Merge k Sorted Lists↗(opens LeetCode in a new tab)

   A heap of k list heads always holds the next smallest node.

   Hard
10. Find Median from Data Stream↗(opens LeetCode in a new tab)

    Two heaps hold the lower and upper halves, balanced in size.

    Hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Recap

• Use it when you need the k best, a running best, or always the cheapest next item.
• Top k largest: min-heap of size k. Top k smallest: max-heap of size k.
• Merge k sorted: one candidate per list in the heap. Running median: two heaps.
• Cost: O(log n) per push or pop, O(n log k) for top k, O(n) to heapify.
• Know your language: Python is min-only, Java and C# take comparators or priorities, Go needs container/heap, TypeScript needs your own.