K-Way Merge

Merge K Sorted Lists

Put the first element of each list into a min-heap. Pop the smallest, append to result, push its successor from the same list. Repeat until the heap is empty. O(n log K) where n = total elements.

O(n log k)

O(k)

How It Works

Merging K sorted lists with a heap generalizes the two-list merge. Seed a min-heap with the first element of every list, each entry remembering which list it came from. Repeatedly pop the smallest element, append it to the output, and push that element's successor from the same list, if any. The heap always holds at most one candidate per list — exactly the frontier of the merge — so the global minimum of all remaining elements is always at the top.

With n total elements, each is pushed and popped once at O(log K) apiece, giving O(n log K) time and O(K) auxiliary space. Naively merging lists one into another degrades to O(nK), and concatenating then sorting costs O(n log n); the heap wins because it never compares more than the K frontier candidates. A divide-and-conquer pairwise merge achieves the same O(n log K) bound without a heap.

Step-by-Step Visualization

Merge 3 sorted lists: [1,4,5], [1,3,4], [2,6]

Heap[1, 1, 2]

1/3

Code

Java

static List<Integer> mergeKLists(List<List<Integer>> lists) {
  // Simplified: flatten and sort (optimal uses min-heap)
  List<Integer> all = new ArrayList<>();
  for (List<Integer> list : lists) all.addAll(list);
  Collections.sort(all);
  return all;
}

// Optimal: use a PriorityQueue with (value, listIndex, nodeIndex)

Tips & Gotchas

1Put first element from each of K lists into a min-heap

2Pop the minimum, add it to result

3Push the next element from the same list

Practice Problems

1Merge K Sorted Lists
2Kth Smallest Element in a Sorted Matrix
3Find K Pairs with Smallest Sums
4Ugly Number II

About the K-Way Merge Pattern

Merge K sorted lists into one sorted output. Use a min-heap to always know which list has the smallest current element. Pop the smallest, add it to the result, and push the next element from that list.

Key insight

Need the K largest? Use a min-heap of size K — anything larger than the min gets in. For median, split into two heaps: max-heap for lower half, min-heap for upper half.

Common Heap Interview Problems

Kth Largest Element
Top K Frequent Elements
Find Median from Data Stream
Merge K Sorted Lists
Task Scheduler
K Closest Points to Origin

Frequently Asked Questions

Why is the complexity O(n log K) and not O(n log n)?

The heap never holds more than K entries — one frontier element per list — so every push and pop costs O(log K). Since each of the n elements passes through the heap exactly once, the total is O(n log K), which is significantly better than sorting when K is much smaller than n.

How does this apply to a sorted matrix or to pairs of arrays?

Treat each row as one sorted list: seed the heap with each row's first element and push the next element of the popped row. For K smallest pairs, seed with (a[i], b[0]) pairs and advance the b index on each pop. The pattern is identical — the heap tracks a small frontier of candidates.

What is a common bug when pushing tuples into the heap?

In Python, tuples compare element by element, so if two values tie the comparison falls through to the next field — which may be an uncomparable object like a ListNode and raise a TypeError. Insert a unique counter or index as the tie-breaking second field.