Pattern 2: Merging K sources (k-way merge)

In the Linked List section, you merged two sorted lists by comparing the heads. And to merge K lists? Comparing K heads at every step would be O(K) per element. The heap does it in O(log K) — and that is your right tool for the famous Merge k Sorted Lists.

🎯

Try it first: Merge k Sorted Lists

Before reading the theory, try to solve it. You can start with brute force, you can fail — the point is to feel the problem. The theory comes right below.

Given k sorted lists (here, as arrays), merge them all into a single sorted list and return it.

Example: [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6].

(This is the "merge k" you saw in the Linked List section — now with the right tool: the heap.)

Carregando editor…

Tried it? Concatenating everything and sorting works (O(N log N)), but it throws away the fact that each list is already sorted. The theory below uses the heap to take advantage of that.

The theory: the heap picks the next smallest

The next element of the result is always the smallest among the heads of the K lists. Instead of looking at all K heads at every step, keep them in a min-heap: the top is the smallest, removed in O(log K).

The key piece: when storing a head in the heap, also store which list it came from (and its position), so you can refill the next one from that list afterward:

min-heap with the 1st head of each list (value, which list, index)
while the heap is not empty:
    (value, list, index) = remove the smallest
    add value to the result
    if there is a next one in that list:
        push (next value, same list, index+1)

The heap has at most K elements (one head per list), and each of the N total elements enters and leaves once. That is why the cost is O(N log K) — much better than comparing K heads per element (O(N·K)) or concatenating and sorting (O(N log N), which is larger when K ≪ N).

Revisiting two problems with the right tool

This section revisits problems you have already solved — now with the heap:

Merge k Sorted Lists (Linked List section): there you would merge pair by pair (a tournament, O(N log K)); the heap gives the same O(N log K) in a single pass, keeping the K heads.
Meeting Rooms II (Intervals section): there we used an event sweep; the other classic solution is a min-heap of the end times of the meetings in progress — the size of the heap is the number of rooms. Same answer, new tool.

The lesson: the heap is the structure that answers "what is the next/smallest right now?" as the set changes. Several problems you solved with specific tricks have a clean, general solution with a heap.

Why not concatenate and sort?

Concatenating the K lists and sorting is O(N log N) and ignores that each list is already sorted. The heap takes advantage of that order: since the next smallest can only come from one of the K heads, the work per element drops from log N to log K. When you have many elements in few lists (K ≪ N), the difference is real.

🧠 Review quiz

0/4

1. In the k-way merge, why is the next element of the result always among the K heads?

2. Why store 'which list' each element came from in the heap?

3. Why is the k-way merge with a heap O(N log K)?

4. Meeting Rooms II (Intervals section) has a heap-based solution. Which one?

Summary

k-way merge: the next smallest is the minimum of the K heads → min-heap of size K, storing the origin of each element.
O(N log K) — takes advantage of each source already being sorted (better than concatenate+sort when K ≪ N).
The heap revisits Merge k Lists and Meeting Rooms II with a clean solution.

Next lesson: balancing two halves to find the median of a stream — two heaps.

All lessons in this section