Merge K Sorted Lists Using Min Heap in DSA Javascript - Execution Trace

Concept Flow - Merge K Sorted Lists Using Min Heap

Create min heap

↓

Insert first node of each list

↓

While heap not empty

↓

Extract min node

↓

Add min node to merged list

↓

If min node has next, insert next into heap

↓

Repeat until heap empty

↓

Return merged list head

Build a min heap with first nodes, repeatedly extract smallest, add to merged list, and insert next nodes until all lists merge.

Execution Sample

DSA Javascript

function mergeKLists(lists) {
  const minHeap = new MinHeap();
  for (const node of lists) if (node) minHeap.insert(node);
  let dummy = new ListNode(0), current = dummy;
  while (!minHeap.isEmpty()) {
    let minNode = minHeap.extractMin();
    current.next = minNode;
    current = current.next;
    if (minNode.next) minHeap.insert(minNode.next);
  }
  return dummy.next;
}

Merges k sorted linked lists by using a min heap to always pick the smallest node.

Execution Table

Step	Operation	Nodes in Heap (values)	Extracted Node	Merged List State	Heap After Operation
1	Insert first nodes of all lists	[1, 2, 3]	None	Empty	[1, 2, 3]
2	Extract min node	[1, 2, 3]	1	1 -> null	[2, 3]
3	Insert next of extracted node (1.next=4)	[2, 3]	None	1 -> null	[2, 3, 4]
4	Extract min node	[2, 3, 4]	2	1 -> 2 -> null	[3, 4]
5	Insert next of extracted node (2.next=5)	[3, 4]	None	1 -> 2 -> null	[3, 4, 5]
6	Extract min node	[3, 4, 5]	3	1 -> 2 -> 3 -> null	[4, 5]
7	Insert next of extracted node (3.next=6)	[4, 5]	None	1 -> 2 -> 3 -> null	[4, 5, 6]
8	Extract min node	[4, 5, 6]	4	1 -> 2 -> 3 -> 4 -> null	[5, 6]
9	Insert next of extracted node (4.next=null)	[5, 6]	None	1 -> 2 -> 3 -> 4 -> null	[5, 6]
10	Extract min node	[5, 6]	5	1 -> 2 -> 3 -> 4 -> 5 -> null	[6]
11	Insert next of extracted node (5.next=null)	[6]	None	1 -> 2 -> 3 -> 4 -> 5 -> null	[6]
12	Extract min node	[6]	6	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null	[]
13	Heap empty, stop	[]	None	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null	[]

💡 Heap is empty, all nodes merged into one sorted list.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	Final
minHeap	[]	[2,3]	[3,4]	[4,5]	[5,6]	[6]	[]	[]
mergedList	Empty	1 -> null	1 -> 2 -> null	1 -> 2 -> 3 -> null	1 -> 2 -> 3 -> 4 -> null	1 -> 2 -> 3 -> 4 -> 5 -> null	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
current	dummy	Node 1	Node 2	Node 3	Node 4	Node 5	Node 6	Node 6

Key Moments - 3 Insights

Why do we insert only the next node of the extracted node into the heap?

Because each list is sorted, after extracting the smallest node, only its next node can be the next smallest candidate. This keeps the heap size small and ensures correct order, as shown in steps 3, 5, 7, 9, and 11.

What happens if one of the input lists is empty?

If a list is empty, its first node is null and not inserted into the heap initially (step 1). The algorithm continues with the other lists without errors, merging only available nodes.

How does the heap help in merging k sorted lists efficiently?

The heap always keeps the smallest current nodes from each list at the top, so extracting min gives the next smallest node globally. This avoids scanning all lists repeatedly, as seen in the heap states in the execution table.

Visual Quiz - 3 Questions

Look at the execution table, what is the heap state after step 5?

A [3, 4, 5]

B [2, 3, 4]

C [4, 5, 6]

D [5, 6]

💡 Hint

Check the 'Heap After Operation' column for step 5 in the execution table.

At which step does the merged list first contain the node with value 3?

A Step 4

B Step 6

C Step 8

D Step 2

💡 Hint

Look at the 'Merged List State' column and find when '3' appears.

If the input lists had no next nodes (all single nodes), how would the heap size change after each extraction?

A Heap size increases after each extraction

B Heap size stays the same

C Heap size decreases by one each extraction

D Heap size becomes zero immediately

💡 Hint

Refer to the heap insertions after extraction steps in the execution table.

Concept Snapshot

Merge K Sorted Lists Using Min Heap:
- Insert first node of each list into min heap
- Extract min node from heap and add to merged list
- Insert next node of extracted node into heap if exists
- Repeat until heap empty
- Result is one merged sorted linked list

Full Transcript

This visualization shows how to merge k sorted linked lists using a min heap. First, the algorithm inserts the first node of each list into the min heap. Then, it repeatedly extracts the smallest node from the heap and adds it to the merged list. If the extracted node has a next node, that next node is inserted into the heap. This process continues until the heap is empty, meaning all nodes have been merged. The execution table tracks the heap contents, extracted nodes, and the merged list state at each step. The variable tracker shows how the heap and merged list pointers change over time. Key moments clarify why only next nodes are inserted and how empty lists are handled. The visual quiz tests understanding of heap states and merged list growth. This method efficiently merges k sorted lists by always choosing the smallest available node using the 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