Algorithms from zero

K-way merge and merging sorted lists

Crux Merge k sorted lists using a min-heap. Store each list''''s head in a min-heap, pop the smallest, append to output, push the next element. Time O(n log k), space O(k). Beats naive O(nk) approach.

◷ 36 min

You have k sorted lists. Your task: merge them into one sorted list. Naive answer: scan the head of all k lists, find the smallest, append it to the output, move forward. Repeat until all are exhausted. But scanning k heads every step is O(nk)—slow. The insight: maintain a min-heap of size k holding the head of each list. Pop the smallest head, append it, push the next element from that same list. The heap keeps the k smallest candidates at the top, so each pop/push is O(log k). Total time: O(n log k). Space: O(k). This is the k-way merge pattern.

Goal

After this lesson you can solve the merge k sorted lists problem using a min-heap: initialize a heap with the head of each list (tracking which list each head came from), pop the smallest, append to the output, and push the next element from the same list. You understand why this works: the heap always holds one candidate from each of the k lists, and the root is always the overall minimum at that moment. You can explain the time complexity O(n log k) and space complexity O(k), and why this beats the naive O(nk) approach. You can recognize the “merge k sorted X” shape on LeetCode (linked lists, arrays, iterators), trace the algorithm step by step on concrete input, and code it. You understand the smallest-range and merge-sorted-arrays variants. This is your final heap lesson; next is graphs.

The idea

The problem: merge k sorted lists

You are given k sorted lists. Your task: merge them into one sorted output list, preserving order.

Example:

Lists: [1, 4, 5], [1, 3, 4], [2, 6]
Merged: [1, 1, 2, 3, 4, 4, 5, 6]

Naive approach: scan all heads every step

For each step:

Scan the head of all k lists to find the minimum.
Append the minimum to the output.
Move the pointer in that list forward.

Time: O(n) steps, and each step scans k heads in O(k). Total: O(nk). This is slow when k is large.

The heap insight: maintain a size-k heap of heads

Instead of scanning all k heads, use a min-heap to track them. Here is the algorithm:

Create a min-heap.
For each of the k lists, push its head (the first element) into the heap. Store with each heap entry the list index and the current position in that list, so you know which list to pull from next.
While the heap is not empty:
- Pop the minimum from the heap.
- Append it to the output.
- If that list has a next element, push it into the heap (same list index, next position).
The output is now merged and sorted.

Why does this work? At any step, the heap holds exactly one candidate from each of the k lists. The root is the overall minimum among these candidates. When you pop it and push the next element from the same list, the heap maintains the invariant: always the k smallest candidates visible so far, one per list. Each pop/push is O(log k), and you do n total pops, so O(n log k) overall.

Example: merge three lists [1, 4, 5], [1, 3, 4], [2, 6]

Min-heap holds (value, list_index, position):

Initialize: push (1, list 0, pos 0), (1, list 1, pos 0), (2, list 2, pos 0). Heap: min is (1, 0, 0).
Pop (1, 0, 0), append 1 to output. Push (4, 0, 1). Output: [1]. Heap min: (1, 1, 0).
Pop (1, 1, 0), append 1. Push (3, 1, 1). Output: [1, 1]. Heap min: (2, 2, 0).
Pop (2, 2, 0), append 2. Push (6, 2, 1). Output: [1, 1, 2]. Heap min: (3, 1, 1).
Pop (3, 1, 1), append 3. Push (4, 1, 2). Output: [1, 1, 2, 3]. Heap min: (4, 0, 1).
Pop (4, 0, 1), append 4. Push (5, 0, 2). Output: [1, 1, 2, 3, 4]. Heap min: (4, 1, 2).
Pop (4, 1, 2), append 4. List 1 exhausted. Output: [1, 1, 2, 3, 4, 4]. Heap min: (5, 0, 2).
Pop (5, 0, 2), append 5. List 0 exhausted. Output: [1, 1, 2, 3, 4, 4, 5]. Heap min: (6, 2, 1).
Pop (6, 2, 1), append 6. List 2 exhausted. Output: [1, 1, 2, 3, 4, 4, 5, 6]. Heap empty. Done.

Final: [1, 1, 2, 3, 4, 4, 5, 6]. ✓

Why heap size stays at k

At most, the heap holds one element from each of the k lists. When you pop one and push another (from the same list), the heap size does not grow. If a list is exhausted, you do not push, so the heap shrinks. The heap never exceeds k.

Flagship shape: merge k sorted linked lists

A common LeetCode problem: given k sorted linked lists, merge them. The algorithm is identical. Instead of arrays, you traverse pointers. Each heap entry stores the node, not just the value. You pop the min node, append it, and push its next node.

Variant: smallest range

Given k arrays, find the smallest range that includes at least one element from each array. Solution: use a similar heap to track the current element from each array. Maintain the minimum and maximum of the current k elements. The range [min, max] is a candidate answer. Pop the min and push the next from that array. Keep track of the smallest range seen. Time: O(n log k).

Variant: merge sorted arrays (different sizes)

k arrays of different sizes. Merge them in O(n log k) time using the same heap approach. n = total elements across all arrays.

The code

Merging k sorted arrays using a min-heap


      1
      function mergeKSortedLists(lists) {
    

      2
      // Min-heap holds [value, listIndex, position]
    

      3
      const minHeap = new MinPriorityQueue();
    

      4
      const result = [];
    

      5
       
    

      6
      // Push the head of each list
    

      7
      for (let i = 0; i < lists.length; i++) {
    

      8
        if (lists[i].length > 0) {
    

      9
          // Store: value, list index, position in that list
    

      10
          minHeap.insert([lists[i][0], i, 0], lists[i][0]);
    

      11
        }
    

      12
      }
    

      13
       
    

      14
      // Pop min, append, push next from same list
    

      15
      while (!minHeap.isEmpty()) {
    

      16
        const [value, listIdx, pos] = minHeap.extractMin();
    

      17
        result.push(value);
    

      18
        
    

      19
        // If there is a next element in this list, push it
    

      20
        if (pos + 1 < lists[listIdx].length) {
    

      21
          const nextValue = lists[listIdx][pos + 1];
    

      22
          minHeap.insert([nextValue, listIdx, pos + 1], nextValue);
    

      23
        }
    

      24
      }
    

      25
       
    

      26
      return result;
    

      27
      }
    

      28
       
    

      29
      // Example
    

      30
      const lists = [[1, 4, 5], [1, 3, 4], [2, 6]];
    

      31
      const merged = mergeKSortedLists(lists);
    

      32
      console.log(merged); // [1, 1, 2, 3, 4, 4, 5, 6]

L2 Min-heap where the key is the value itself. Each entry is [value, listIndex, position].
L7 For each of k lists, insert the first element (if the list is non-empty).
L8 Store the value, the list it came from, and its position in that list.
L15 While heap is not empty, pop the minimum value (always at root).
L19 Append to result.
L22 If the same list has a next element, push it. If not, that list is exhausted.
L28 The output is now merged and sorted.

Merge k sorted linked lists

class Node {
constructor(val, next = null) {
  this.val = val;
  this.next = next;
}
}

class MinPriorityQueue {
constructor() {
  this.heap = [];
}

insert(item, priority) {
  this.heap.push(item);
  this.siftUp(this.heap.length - 1);
}

extractMin() {
  const root = this.heap[0];
  this.heap[0] = this.heap[this.heap.length - 1];
  this.heap.pop();
  if (this.heap.length > 0) {
    this.siftDown(0);
  }
  return root;
}

isEmpty() {
  return this.heap.length === 0;
}

siftUp(index) {
  while (index > 0) {
    const parentIdx = Math.floor((index - 1) / 2);
    if (this.heap[index][0] < this.heap[parentIdx][0]) {
      [this.heap[index], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[index]];
      index = parentIdx;
    } else {
      break;
    }
  }
}

siftDown(index) {
  while (true) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;

if (left < this.heap.length && this.heap[left][0] < this.heap[smallest][0]) {
      smallest = left;
    }
    if (right < this.heap.length && this.heap[right][0] < this.heap[smallest][0]) {
      smallest = right;
    }

if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    } else {
      break;
    }
  }
}
}

function mergeKLinkedLists(lists) {
const minHeap = new MinPriorityQueue();

// Insert the head of each list
for (let i = 0; i < lists.length; i++) {
  if (lists[i]) {
    // Store: [node, listIndex] with priority = node.val
    minHeap.insert([lists[i], i]);
  }
}

const dummyHead = new Node(-1);
let current = dummyHead;

while (!minHeap.isEmpty()) {
  const [node, listIdx] = minHeap.extractMin();
  current.next = node;
  current = current.next;
  
  // If this node has a next, push it
  if (node.next) {
    minHeap.insert([node.next, listIdx]);
  }
}

return dummyHead.next;
}

// Example: create three linked lists
const list1 = new Node(1, new Node(4, new Node(5)));
const list2 = new Node(1, new Node(3, new Node(4)));
const list3 = new Node(2, new Node(6));

const merged = mergeKLinkedLists([list1, list2, list3]);

// Convert to array for display
const result = [];
let curr = merged;
while (curr) {
result.push(curr.val);
curr = curr.next;
}
console.log(result);

Output

Step-by-step trace


      1
      const lists = [[1, 4, 5], [1, 3, 4], [2, 6]];
    

      2
      const minHeap = new MinPriorityQueue();
    

      3
      const result = [];
    

      4
      // Init: push heads of all lists
    

      5
      for (const [val, idx] of [[1,0], [1,1], [2,2]]) minHeap.insert(val, idx);
    

      6
      while (!minHeap.isEmpty()) {
    

      7
        const [val, idx] = minHeap.extractMin();
    

      8
        result.push(val);
    

      9
        if (hasNext(lists[idx])) minHeap.insert(nextVal(lists[idx]), idx);
    

      10
      }

Complexity

K-way merge with a min-heap of size k

You have n total elements across all k lists.

For each of the n elements:

ExtractMin: O(log k) (the heap holds at most k elements).
Insert (the next element from the same list): O(log k).

Total: n elements × (extract + insert) = n × O(log k) = O(n log k) time.

Space: The heap holds at most k elements (one head from each list), so O(k) space.

Comparison with naive approach

Naive: for each of n elements, scan all k heads to find the minimum. Time: O(nk). Space: O(1) (if you do not count the input).

K-way merge with heap: O(n log k) time, O(k) space.

When is the heap approach better?

Always. O(n log k) is strictly better than O(nk) because log k ≤ n for reasonable k (and usually log k ≪ n).
Example: n = 1,000,000 elements, k = 100 lists. O(n log k) = 1,000,000 × 6.6 ≈ 6.6 million operations. O(nk) = 1,000,000 × 100 = 100 million operations. Heap is ~15 times faster.

Why not other approaches?

Pairwise merge (merge two lists, then merge result with the third, etc.): O(n log k) but with larger constants. Heap is simpler.
Sort all elements globally: O(n log n) time, O(n) space. Worse than O(n log k) when k ≪ n.

Practice 0 / 6

To merge k sorted lists, what is the main purpose of storing the list index and position in each heap entry?

In the k-way merge algorithm, what does the heap invariant guarantee at each step?

You are merging k = 5 sorted lists with n = 1,000,000 total elements. What is the approximate time complexity in operations, using log₂(5) ≈ 2.3?

What is the space complexity of the k-way merge algorithm?

Given three lists [1, 5, 9], [2, 6, 10], [3, 7, 11], what is the first element popped from the min-heap?

After popping (1, L0) and pushing (5, L0) in the previous example, what is the next minimum popped?

lesson.inset.undefined

Why k-way merge matters. Real systems often need to combine sorted data from multiple sources: merging k log files sorted by timestamp, merging results from k database shards sorted by ID, merging k sorted iterators in a data pipeline. You cannot afford to store all data in memory, so you must stream through one element at a time. A k-way heap lets you merge online in O(n log k) time and O(k) space, processing each element exactly once.

lesson.inset.undefined

Storing the entire remaining list instead of just the head. It is tempting to store the entire tail of the list in the heap. That wastes space and makes comparisons slow. Instead, store only the node/value itself and its list index/position. When you pop it, you compute or fetch the next element on demand. The heap never holds more than k elements.

lesson.inset.undefined

Empty lists. If some input lists are empty, do not push them into the heap. The algorithm handles k-m non-empty lists correctly: the heap size grows to the number of non-empty lists, and the complexity is O(n log (k-m)). If all lists are empty, the output is empty. If k = 1, there is only one list, so just return it.

lesson.inset.undefined

Smallest-range variant. Given k arrays, find the smallest range [a, b] such that each array contributes at least one element. Maintain the current min and max among the k heads. The range [min, max] is a candidate answer. Pop the min, push the next from that array, update the range. Time: O(n log k). Space: O(k).

Check yourself

Quiz

Explain the k-way merge algorithm and its time complexity. Why is it O(n log k) and not O(nk)?

Recap

To merge k sorted lists, maintain a min-heap of size k holding one head from each list. Pop the minimum head, append it to output, push the next element from the same list. The heap invariant ensures the root is always the minimum among the k current heads. Time: O(n log k). Space: O(k). This is far better than the naive O(nk) approach (scanning all k heads per step). The same pattern solves merge k sorted linked lists, smallest-range, and merge k sorted arrays. Next: unit 09 (graphs), where you will explore nodes and edges, BFS, DFS, and shortest paths.

Continue the climb ↑Heaps: multiple-choice review