Merging K Sorted Lists
What You'll Learn
You'll learn how to efficiently combine multiple sorted lists into one sorted list using a min-heap to track candidates.
The Problem
Imagine you have k sorted lists (or arrays), and you need to merge them into a single sorted result. A naive approach might repeatedly scan all lists for the smallest element, but that's wasteful—most lists won't have the current minimum.
The Heap-Based Solution
The key insight: at any moment, the next smallest element must be at the front of one of the k lists. We only need to compare k candidates (one per list), not every remaining element.
Here's the strategy:
-
Initialize: Insert the first element from each list into a min-heap. Each heap entry tracks both the value and which list it came from.
-
Repeatedly extract the minimum: Pull the smallest element from the heap and add it to the result.
-
Refill the heap: When you extract an element from list
i, immediately insert the next element from listi(if any remain) into the heap. -
Continue until the heap is empty (all lists exhausted).
Why This Works
The min-heap always contains the "front-runner" from each active list. Each heap operation (insert, extract-min) takes O(log k) time. If the total number of elements across all lists is n, you perform n extractions and up to n insertions.
Time complexity: O(n log k)
Space complexity: O(k) for the heap
This is far better than the O(nk) naive approach when k is small compared to n.
Analogy
Think of k checkout lines at a store. You're the manager calling people to a single service desk. You always call the person at the front of whichever line has been waiting longest (smallest timestamp). The heap tracks those k "next customers."
Key Takeaway: Use a min-heap to efficiently merge k sorted lists by maintaining only the current minimum candidate from each list, achieving O(n log k) time complexity.