Merge K Sorted Lists Using Min Heap in DSA Javascript

Mental Model

We combine many sorted lists into one sorted list by always picking the smallest current element from all lists using a min heap.

Analogy: Imagine you have K friends each reading a sorted book. You want to write down all the words in order. You ask each friend for their current word, pick the smallest word, write it down, then ask that friend for their next word. Repeat until all words are written.

Lists:
List1: 1 -> 4 -> 7 -> null
List2: 2 -> 5 -> 8 -> null
List3: 3 -> 6 -> 9 -> null

MinHeap (initial): [1, 2, 3]

Merged List: null

Dry Run Walkthrough

Input: lists: [1->4->7, 2->5->8, 3->6->9]

Goal: Merge all 3 sorted lists into one sorted list: 1->2->3->4->5->6->7->8->9

Step 1: Insert first nodes of all lists into min heap

MinHeap: [1, 2, 3]
Merged List: null

Why: We start by knowing the smallest elements from each list to pick the smallest overall

Step 2: Extract min (1) from heap and add to merged list; insert next node (4) from list1 into heap

MinHeap: [2, 3, 4]
Merged List: 1 -> null

Why: We add smallest element to merged list and bring next candidate from same list

Step 3: Extract min (2) from heap and add to merged list; insert next node (5) from list2 into heap

MinHeap: [3, 4, 5]
Merged List: 1 -> 2 -> null

Why: Continue picking smallest and replenishing heap from lists

Step 4: Extract min (3) from heap and add to merged list; insert next node (6) from list3 into heap

MinHeap: [4, 5, 6]
Merged List: 1 -> 2 -> 3 -> null

Why: Keep merging by always picking smallest current element

Step 5: Extract min (4) from heap and add to merged list; insert next node (7) from list1 into heap

MinHeap: [5, 6, 7]
Merged List: 1 -> 2 -> 3 -> 4 -> null

Why: Add next smallest and continue replenishing heap

Step 6: Extract min (5) from heap and add to merged list; insert next node (8) from list2 into heap

MinHeap: [6, 7, 8]
Merged List: 1 -> 2 -> 3 -> 4 -> 5 -> null

Why: Continue merging in sorted order

Step 7: Extract min (6) from heap and add to merged list; insert next node (9) from list3 into heap

MinHeap: [7, 8, 9]
Merged List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Why: Keep picking smallest and adding next nodes

Step 8: Extract min (7) from heap and add to merged list; list1 has no more nodes

MinHeap: [8, 9]
Merged List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null

Why: Add remaining elements from heap as lists finish

Step 9: Extract min (8) from heap and add to merged list; list2 has no more nodes

MinHeap: [9]
Merged List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null

Why: Continue until all nodes are merged

Step 10: Extract min (9) from heap and add to merged list; list3 has no more nodes

MinHeap: []
Merged List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Why: All nodes merged, heap empty

Result:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Annotated Code

DSA Javascript

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

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

  insert(node) {
    this.heap.push(node);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex].val <= this.heap[index].val) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return min;
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;
    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let smallest = index;

      if (left < length && this.heap[left].val < this.heap[smallest].val) {
        smallest = left;
      }
      if (right < length && this.heap[right].val < this.heap[smallest].val) {
        smallest = right;
      }
      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }

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

function mergeKLists(lists) {
  const minHeap = new MinHeap();

  // Insert first node of each list into min heap
  for (const node of lists) {
    if (node !== null) {
      minHeap.insert(node);
    }
  }

  const dummy = new ListNode(0);
  let current = dummy;

  // Extract min and add next nodes until heap is empty
  while (!minHeap.isEmpty()) {
    const minNode = minHeap.extractMin();
    current.next = minNode;
    current = current.next;
    if (minNode.next !== null) {
      minHeap.insert(minNode.next);
    }
  }

  return dummy.next;
}

// Driver code using dry_run input
const list1 = new ListNode(1, new ListNode(4, new ListNode(7)));
const list2 = new ListNode(2, new ListNode(5, new ListNode(8)));
const list3 = new ListNode(3, new ListNode(6, new ListNode(9)));

const mergedHead = mergeKLists([list1, list2, list3]);

// Print merged list
let output = '';
let curr = mergedHead;
while (curr !== null) {
  output += curr.val + ' -> ';
  curr = curr.next;
}
output += 'null';
console.log(output);

for (const node of lists) { if (node !== null) { minHeap.insert(node); } }

Insert first nodes of all lists into min heap to start merging

while (!minHeap.isEmpty()) { const minNode = minHeap.extractMin(); current.next = minNode; current = current.next; if (minNode.next !== null) { minHeap.insert(minNode.next); } }

Repeatedly extract smallest node, add to merged list, and insert next node from same list

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Complexity Analysis

Time: O(N log K) because we process all N nodes and each heap operation takes O(log K) where K is number of lists

Space: O(K) for the heap storing one node from each list at a time

vs Alternative: Naive merging by repeatedly merging two lists at a time takes more time (O(KN)) compared to min heap approach which is more efficient

Edge Cases

Empty input lists array

Returns null as there are no nodes to merge

DSA Javascript

if (node !== null) { minHeap.insert(node); }

Some lists are empty (null)

Only non-empty lists contribute nodes; empty lists ignored

DSA Javascript

if (node !== null) { minHeap.insert(node); }

All lists empty

Returns null as no nodes exist

DSA Javascript

if (node !== null) { minHeap.insert(node); }

When to Use This Pattern

When you need to merge multiple sorted lists efficiently, use a min heap to always pick the smallest current element from all lists.

Common Mistakes

Mistake: Not inserting the next node of the extracted node back into the heap
Fix: After extracting minNode, check if minNode.next exists and insert it into the heap

Mistake: Using a max heap or sorting all nodes at once instead of incremental merging
Fix: Use a min heap to always pick the smallest node incrementally for efficiency

Summary

Merges K sorted linked lists into one sorted linked list using a min heap.

Use when you have multiple sorted lists and want to merge them efficiently.

The key is to always pick the smallest current node from all lists using a min heap.

Practice

1. What is the main purpose of using a min heap when merging K sorted lists?

easy

A. To sort each individual list before merging

B. To efficiently find the smallest element among the heads of all lists

C. To store all elements from all lists at once

D. To reverse the order of elements in each list

Solution

1. Step 1: Understand the role of min heap in merging

   A min heap helps quickly find the smallest element among multiple candidates, which is essential when merging sorted lists.

2. Step 2: Apply this to merging K sorted lists

   By pushing the first element of each list into the min heap, we can always extract the smallest element efficiently to build the merged list.

3. Final Answer:

   To efficiently find the smallest element among the heads of all lists -> Option B

4. Quick Check:

   Min heap = smallest element finder [OK]

Hint: Min heap always gives smallest element fast [OK]

Common Mistakes:

• Thinking min heap sorts entire lists
• Assuming min heap stores all elements at once
• Confusing min heap with max heap

2. Which of the following is the correct way to insert an element into a min heap in JavaScript?

easy

A. heap.push(element); heapifyUp();

B. heap.pop(); heapifyDown();

C. heap.unshift(element); heapifyDown();

D. heap.shift(); heapifyUp();

Solution

1. Step 1: Understand insertion in min heap

   To insert, add the element at the end (push), then move it up to maintain heap property (heapifyUp).

2. Step 2: Match with options

   heap.push(element); heapifyUp(); correctly shows push followed by heapifyUp, which is the standard insertion method.

3. Final Answer:

   heap.push(element); heapifyUp(); -> Option A

4. Quick Check:

   Insert = push + heapifyUp [OK]

Hint: Insert by push then heapify up [OK]

Common Mistakes:

• Using pop or shift to insert
• Calling heapifyDown after insertion
• Using unshift which is inefficient

3. What will be the output of the following code snippet that merges 3 sorted lists using a min heap?

const lists = [[1,4,5],[1,3,4],[2,6]];
function mergeKLists(lists) {
  const minHeap = [];
  const result = [];
  for (let i = 0; i < lists.length; i++) {
    if (lists[i].length > 0) minHeap.push({ val: lists[i][0], listIndex: i, elementIndex: 0 });
  }
  minHeap.sort((a,b) => a.val - b.val);
  while (minHeap.length > 0) {
    const smallest = minHeap.shift();
    result.push(smallest.val);
    const nextIndex = smallest.elementIndex + 1;
    if (nextIndex < lists[smallest.listIndex].length) {
      minHeap.push({ val: lists[smallest.listIndex][nextIndex], listIndex: smallest.listIndex, elementIndex: nextIndex });
      minHeap.sort((a,b) => a.val - b.val);
    }
  }
  return result;
}
console.log(mergeKLists(lists));

medium

A. [1,4,5,1,3,4,2,6]

B. [1,2,3,4,5,6]

C. [1,1,2,3,4,4,5,6]

D. [6,5,4,4,3,2,1,1]

Solution

1. Step 1: Initialize min heap with first elements

   minHeap starts with {1,0,0}, {1,1,0}, {2,2,0} sorted as [1,1,2].

2. Step 2: Extract smallest and add next elements

   Extract 1 from list 0, add 4; extract 1 from list 1, add 3; extract 2 from list 2, add 6; continue until all elements merged.

3. Final Answer:

   [1,1,2,3,4,4,5,6] -> Option C

4. Quick Check:

   Merged sorted list = [1,1,2,3,4,4,5,6] [OK]

Hint: Track smallest and add next from same list [OK]

Common Mistakes:

• Not sorting minHeap after each insertion
• Forgetting to add next element from same list
• Returning concatenated lists instead of merged

4. Identify the bug in the following code snippet for merging K sorted lists using a min heap:

function mergeKLists(lists) {
  const minHeap = [];
  const result = [];
  for (let i = 0; i < lists.length; i++) {
    minHeap.push({ val: lists[i][0], listIndex: i, elementIndex: 0 });
  }
  minHeap.sort((a,b) => a.val - b.val);
  while (minHeap.length > 0) {
    const smallest = minHeap.shift();
    result.push(smallest.val);
    const nextIndex = smallest.elementIndex + 1;
    if (nextIndex < lists[smallest.listIndex].length) {
      minHeap.push({ val: lists[smallest.listIndex][nextIndex], listIndex: smallest.listIndex, elementIndex: nextIndex });
      minHeap.sort((a,b) => a.val - b.val);
    }
  }
  return result;
}

medium

A. Not initializing minHeap with first elements of lists

B. Not pushing the first element of each list into minHeap

C. Using shift() instead of pop() to get smallest element

D. Missing sorting minHeap after pushing new element inside the loop

Solution

1. Step 1: Check minHeap maintenance inside loop

   After pushing a new element, minHeap must be sorted to keep smallest element at front.

2. Step 2: Identify missing sorting

   The code pushes new elements but does not sort minHeap again, breaking the min heap property.

3. Final Answer:

   Missing sorting minHeap after pushing new element inside the loop -> Option D

4. Quick Check:

   Sort after push to maintain min heap [OK]

Hint: Always re-sort min heap after insertion [OK]

Common Mistakes:

• Forgetting to sort minHeap after push
• Confusing shift() and pop() usage
• Not pushing initial elements into minHeap

5. Given K sorted linked lists, which approach best optimizes the time complexity when merging them using a min heap?

hard

A. Insert only the first element of each list into the min heap, then extract and insert next elements dynamically

B. Insert all elements from all lists into the min heap at once, then extract all

C. Merge lists two at a time without using a min heap

D. Concatenate all lists and sort the combined list

Solution

1. Step 1: Analyze time complexity of inserting all elements at once

   Inserting all elements at once leads to O(N log N) where N is total elements, which is less efficient.

2. Step 2: Understand dynamic insertion approach

   Inserting only first elements and dynamically adding next elements keeps heap size at K, leading to O(N log K) time, which is optimal.

3. Final Answer:

   Insert only the first element of each list into the min heap, then extract and insert next elements dynamically -> Option A

4. Quick Check:

   Dynamic insertion = O(N log K) best [OK]

Hint: Keep heap size small by dynamic insertion [OK]

Common Mistakes:

• Inserting all elements at once causing slow performance
• Ignoring heap size impact on complexity
• Using simple concatenation and sort which is inefficient