Course contentsShow
← Computer Science
Lesson 616 of 2,87214. Heaps and Priority QueuesFree lesson

Merging K Sorted Lists

Efficiently merge k sorted lists using a min-heap to track the smallest element from each list.

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:

  1. 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.

  2. Repeatedly extract the minimum: Pull the smallest element from the heap and add it to the result.

  3. Refill the heap: When you extract an element from list i, immediately insert the next element from list i (if any remain) into the heap.

  4. 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.