Merge K Sorted Lists Using Min Heap in DSA C# - 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 node into heap

Back to While heap not empty↓

Return merged list head

↩Back to While heap not empty

We build a min heap with the first nodes of each list, repeatedly extract the smallest node, add it to the merged list, and insert the next node from that list into the heap until all nodes are merged.

Execution Sample

DSA C#

ListNode MergeKLists(ListNode[] lists) {
  var heap = new MinHeap();
  foreach (var node in lists) if (node != null) heap.Insert(node);
  ListNode dummy = new ListNode(0), current = dummy;
  while (!heap.IsEmpty()) {
    var minNode = heap.ExtractMin();
    current.next = minNode;
    current = current.next;
    if (minNode.next != null) heap.Insert(minNode.next);
  }
  return dummy.next;
}

This code merges k sorted linked lists by using a min heap to always pick the smallest current node.

Execution Table

Step	Operation	Nodes in Heap	Extracted Node	Merged List State	Heap After Operation
1	Insert first nodes of each list	[]	None	Empty	[1, 2, 3]
2	Extract min node	[1, 2, 3]	1	1 -> null	[2, 3]
3	Insert next node 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 node 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 node 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 node 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 node 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, end	[]	None	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null	[]

💡 Heap is empty, all nodes merged into the final list.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	Final
heap	[]	[2,3]	[3,4]	[4,5]	[5,6]	[6]	[]	[]
merged_list	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	points to 1	points to 2	points to 3	points to 4	points to 5	points to 6	points to 6

Key Moments - 3 Insights

Why do we insert only the first node of each list into the heap at the start?

Because the lists are sorted, the first node is the smallest in each list. Inserting only these nodes keeps the heap small and efficient, as shown in step 1 of the execution_table.

What happens when we extract a node from the heap?

We add that node to the merged list and then insert its next node into the heap if it exists. This is shown in steps 2 and 3 where after extracting node 1, node 4 is inserted.

Why does the heap size change during execution?

Because we remove the smallest node and add its next node if available. This keeps the heap size between 0 and k, as seen in the variable_tracker for 'heap'.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, which node is extracted from the heap?

A Node with value 1

B Node with value 2

C Node with value 3

D Node with value 4

💡 Hint

Check the 'Extracted Node' column at step 4 in the execution_table.

At which step does the heap become empty?

A Step 13

B Step 10

C Step 12

D Step 8

💡 Hint

Look at the 'heap' variable in variable_tracker and the 'Heap After Operation' column in execution_table.

If the first node of the second list was null, how would the initial heap change?

A It would contain the same nodes

B It would be empty

C It would contain one less node initially

D It would contain duplicate nodes

💡 Hint

Refer to step 1 in execution_table where first nodes are inserted into the heap.

Concept Snapshot

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

Full Transcript

To merge k sorted linked lists, we use a min heap to always pick the smallest current node. We start by inserting the first node of each list into the heap. Then, we repeatedly extract the smallest node from the heap, add it to the merged list, and if that node has a next node, we insert it into the heap. This process continues until the heap is empty, meaning all nodes are merged. The execution table shows each step with heap contents, extracted nodes, and the merged list state. The variable tracker follows the heap and merged list changes. Key moments clarify why only first nodes are inserted initially, what happens on extraction, and why heap size changes. The visual quiz tests understanding of these steps. This method efficiently merges k sorted lists into one sorted list.

Practice

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

easy

A. To efficiently get the smallest current element among all lists

B. To store all elements in sorted order before merging

C. To reverse the order of elements in each list

D. To count the total number of elements in all lists

Solution

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

   A min heap helps quickly find the smallest element among multiple sorted lists without scanning all elements.

2. Step 2: Why min heap is chosen

   It maintains the smallest element at the top, so we can pick and remove it efficiently while merging.

3. Final Answer:

   To efficiently get the smallest current element among all lists -> Option A

4. Quick Check:

   Min heap = smallest element retrieval [OK]

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

Common Mistakes:

• Thinking min heap stores all elements sorted
• Confusing min heap with max heap
• Using min heap to count elements

2. Which of the following is the correct way to initialize a min heap in C# for merging K sorted lists?

easy

A. var minHeap = new List<int>();

B. var minHeap = new SortedSet<(int val, int listIndex, ListNode node)>();

C. var minHeap = new Queue<ListNode>();

D. var minHeap = new Stack<ListNode>();

Solution

1. Step 1: Identify data structure for min heap

   SortedSet with tuple (value, list index, node) can act as a min heap by sorting elements by value.

2. Step 2: Why other options are incorrect

   List, Queue, and Stack do not maintain sorted order automatically, so they can't serve as min heap.

3. Final Answer:

   var minHeap = new SortedSet<(int val, int listIndex, ListNode node)>(); -> Option B

4. Quick Check:

   SortedSet = min heap structure [OK]

Hint: Use SortedSet with tuples for min heap in C# [OK]

Common Mistakes:

• Using List or Queue as min heap
• Not including value for sorting in tuple
• Confusing Stack with heap

3. What will be the output linked list after merging these 3 sorted lists using a min heap?

List 1: 1 -> 4 -> 5 -> null
List 2: 1 -> 3 -> 4 -> null
List 3: 2 -> 6 -> null

medium

A. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

B. 1 -> 3 -> 4 -> 1 -> 4 -> 5 -> 2 -> 6 -> null

C. 6 -> 5 -> 4 -> 4 -> 3 -> 2 -> 1 -> 1 -> null

D. 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null

Solution

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

   Insert 1 (List1), 1 (List2), 2 (List3) into min heap.

2. Step 2: Extract min and add next nodes

   Extract 1 (List1), add 4; extract 1 (List2), add 3; extract 2 (List3), add 6; continue extracting min and adding next nodes until all lists are merged.

3. Final Answer:

   1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null -> Option D

4. Quick Check:

   Merge sorted lists = sorted combined list [OK]

Hint: Always pick smallest node from heap and add next from same list [OK]

Common Mistakes:

• Not adding next node after extracting min
• Merging lists without sorting
• Confusing order of nodes

4. Given the following code snippet for merging K sorted lists, what is the error?

var minHeap = new SortedSet<(int val, int listIndex, ListNode node)>();
foreach (var list in lists) {
  if (list != null) minHeap.Add((list.val, 0, list));
}
while (minHeap.Count > 0) {
  var min = minHeap.Min;
  minHeap.Remove(min);
  // Add min.node to result
  if (min.node.next != null) {
    minHeap.Add((min.node.next.val, min.listIndex + 1, min.node.next));
  }
}

medium

A. Incrementing listIndex incorrectly when adding next node

B. Not checking if list is null before adding to heap

C. Using SortedSet instead of PriorityQueue

D. Not removing min element from heap

Solution

1. Step 1: Understand listIndex usage

   listIndex should identify which list the node belongs to and remain constant for that list.

2. Step 2: Identify error in incrementing listIndex

   Incrementing listIndex by 1 when adding next node is wrong; it should stay the same to track correct list.

3. Final Answer:

   Incrementing listIndex incorrectly when adding next node -> Option A

4. Quick Check:

   listIndex must not change per node [OK]

Hint: Keep listIndex fixed per list, don't increment per node [OK]

Common Mistakes:

• Changing listIndex for next nodes
• Forgetting to remove min element
• Ignoring null checks

5. You have 4 sorted linked lists with lengths 2, 3, 4, and 5 respectively. Using a min heap, what is the time complexity to merge all lists into one sorted list?

hard

A. O(N + K), where N is total nodes and K is number of lists

B. O(N K), where N is total nodes and K is number of lists

C. O(N log K), where N is total nodes and K is number of lists

D. O(K log N), where N is total nodes and K is number of lists

Solution

1. Step 1: Calculate total nodes and understand K

   Total nodes N = 2 + 3 + 4 + 5 = 14, K = 4 lists.

2. Step 2: Analyze min heap operations

   Each node is pushed and popped once from min heap of size K, so operations take O(log K) each.

3. Step 3: Combine to get total complexity

   Total time = O(N log K) because each of N nodes involves heap operations.

4. Final Answer:

   O(N log K), where N is total nodes and K is number of lists -> Option C

5. Quick Check:

   Heap operations per node = log K [OK]

Hint: Merging K lists with heap = O(N log K) time [OK]

Common Mistakes:

• Assuming O(N K) instead of O(N log K)
• Ignoring heap operation cost
• Confusing N and K roles