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

Concept Flow - Merge K Sorted Lists Using Min Heap

Create min heap

↓

Insert first node of each list into heap

↓

While heap not empty

↓

Extract min node from heap

↓

Add extracted node to merged list

↓

If extracted node has next, insert next into heap

↓

Repeat until all nodes merged

↓

Return merged list head

Start by putting the first node of each list into a min heap. Then repeatedly take the smallest node from the heap, add it to the merged list, and if that node has a next node, add it to the heap. Continue until all nodes are merged.

Execution Sample

DSA Java

ListNode mergeKLists(ListNode[] lists) {
  PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
  for (ListNode node : lists) if (node != null) heap.add(node);
  ListNode dummy = new ListNode(0), tail = dummy;
  while (!heap.isEmpty()) {
    ListNode min = heap.poll();
    tail.next = min;
    tail = tail.next;
    if (min.next != null) heap.add(min.next);
  }
  return dummy.next;
}

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

Execution Table

Step	Operation	Nodes in Heap	Extracted Node	Merged List State	Heap After Operation
1	Insert first nodes of all lists	[]	None	Empty	[1, 2, 3]
2	Extract min node	[1, 2, 3]	1	1 -> null	[2, 3]
3	Insert next of extracted node (1->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->6)	[3, 4]	None	1 -> 2 -> null	[3, 4, 6]
6	Extract min node	[3, 4, 6]	3	1 -> 2 -> 3 -> null	[4, 6]
7	Insert next of extracted node (3->5)	[4, 6]	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->7)	[5, 6]	None	1 -> 2 -> 3 -> 4 -> null	[5, 6, 7]
10	Extract min node	[5, 6, 7]	5	1 -> 2 -> 3 -> 4 -> 5 -> null	[6, 7]
11	Extract min node	[6, 7]	6	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null	[7]
12	Extract min node	[7]	7	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null	[]
13	Heap empty, done	[]	None	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null	[]

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

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	After Step 9	After Step 13
heap	empty	[1,2,3]	[2,3,4]	[3,4,6]	[4,5,6]	[5,6,7]	empty
mergedList	empty	empty	1 -> null	1 -> 2 -> null	1 -> 2 -> 3 -> null	1 -> 2 -> 3 -> 4 -> null	1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
tail	dummy	dummy	node with val 1	node with val 2	node with val 3	node with val 4	node with val 7

Key Moments - 3 Insights

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

Because the lists are sorted, the first node is the smallest in each list. We start merging by comparing these smallest nodes. (See execution_table row 1)

Why do we add the next node of the extracted node back into the heap?

After extracting the smallest node, its next node might be the next smallest candidate. Adding it keeps the heap updated with current smallest nodes. (See execution_table rows 3, 5, 7, 9)

How do we know when merging is complete?

When the heap is empty, it means all nodes from all lists have been extracted and merged. (See execution_table row 13)

Visual Quiz - 3 Questions

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

A Node with value 1

B Node with value 3

C Node with value 2

D Node with value 4

💡 Hint

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

At which step does the heap become empty?

A Step 12

B Step 13

C Step 10

D Step 9

💡 Hint

Look at the 'Nodes in Heap' column and the exit_note in execution_table.

If the next node of the extracted node is null, what happens to the heap?

A We do not add anything to the heap

B We add a null to the heap

C We add the extracted node again

D The heap is cleared

💡 Hint

Refer to the code in execution_sample and the heap state changes in execution_table.

Concept Snapshot

Merge K Sorted Lists Using Min Heap:
- Insert first node of each list into a min heap
- Extract min node, add to merged list
- Insert next node of extracted node 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 and add it to our merged list. If the extracted node has a next node, we insert that next node into the heap. This process continues until the heap is empty, meaning all nodes have been merged. This approach efficiently merges all lists into one sorted list.

Practice

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

easy

A. To efficiently get the smallest element among the heads of all lists

B. To sort each individual list before merging

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 sorted lists by always keeping the smallest element at the top.

2. Step 2: Why min heap is used here

   When merging K sorted lists, we repeatedly pick the smallest current element from all lists. The min heap efficiently supports this operation.

3. Final Answer:

   To efficiently get the smallest element among the heads of 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 sorts entire lists
• Using max heap instead of min heap
• Storing all elements at once in heap

2. Which of the following Java code snippets correctly initializes a min heap for integers?

easy

A. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.reverseOrder());

B. PriorityQueue<Integer> minHeap = new PriorityQueue<>();

C. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());

D. PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.naturalOrder().reversed());

Solution

1. Step 1: Check default behavior of PriorityQueue

   By default, Java's PriorityQueue is a min heap, so new PriorityQueue<>() creates a min heap.

2. Step 2: Analyze other options

   Options A, B, and D create max heaps using reverse order or equivalent. Only C uses the default min heap.

3. Final Answer:

   PriorityQueue<Integer> minHeap = new PriorityQueue<>(); -> Option B

4. Quick Check:

   Default PriorityQueue = min heap [OK]

Hint: Default PriorityQueue is min heap in Java [OK]

Common Mistakes:

• Using reverseOrder() creates max heap, not min heap
• Confusing Comparator.naturalOrder() usage
• Not importing java.util.PriorityQueue

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

List<Integer> l1 = List.of(1, 4, 5);
List<Integer> l2 = List.of(1, 3, 4);
List<Integer> l3 = List.of(2, 6);

PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

minHeap.offer(new int[]{l1.get(0), 0, 0});
minHeap.offer(new int[]{l2.get(0), 1, 0});
minHeap.offer(new int[]{l3.get(0), 2, 0});

List<Integer> result = new ArrayList<>();

while (!minHeap.isEmpty()) {
    int[] curr = minHeap.poll();
    result.add(curr[0]);
    int listIndex = curr[1];
    int elementIndex = curr[2];
    if (elementIndex + 1 < (listIndex == 0 ? l1.size() : listIndex == 1 ? l2.size() : l3.size())) {
        int nextVal = (listIndex == 0 ? l1 : listIndex == 1 ? l2 : l3).get(elementIndex + 1);
        minHeap.offer(new int[]{nextVal, listIndex, elementIndex + 1});
    }
}

System.out.println(result);

medium

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

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

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

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

Solution

1. Step 1: Initialize min heap with first elements

   Heap starts with [1(l1), 1(l2), 2(l3)]. Poll smallest 1 from l1, add next 4 from l1. Then poll 1 from l2, add next 3 from l2, and so on.

2. Step 2: Continue polling and adding next elements

   Sequence of polled elements is 1(l1), 1(l2), 2(l3), 3(l2), 4(l1), 4(l2), 5(l1), 6(l3). This forms the merged sorted list.

3. Final Answer:

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

4. Quick Check:

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

Hint: Poll min, add next from same list until all merged [OK]

Common Mistakes:

• Forgetting to add next element after polling
• Mixing list indices when adding next elements
• Not handling empty lists properly

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

PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);

for (int i = 0; i < lists.size(); i++) {
    if (!lists.get(i).isEmpty()) {
        minHeap.offer(new int[]{lists.get(i).get(0), i, 0});
    }
}

List<Integer> result = new ArrayList<>();

while (!minHeap.isEmpty()) {
    int[] curr = minHeap.poll();
    result.add(curr[0]);
    int listIndex = curr[1];
    int elementIndex = curr[2];
    if (elementIndex + 1 < lists.get(listIndex).size()) {
        minHeap.offer(new int[]{lists.get(listIndex).get(elementIndex + 1), listIndex, elementIndex + 1});
    }
}

medium

A. The result list is not initialized before use

B. The loop does not check for empty lists before adding

C. Comparator reverses order, creating max heap instead of min heap

D. The elementIndex is not incremented correctly when adding next element

Solution

1. Step 1: Analyze the comparator used in PriorityQueue

   The comparator (b[0] - a[0]) reverses natural order, making it a max heap, not a min heap.

2. Step 2: Effect of max heap on merging sorted lists

   Using max heap causes the largest element to be polled first, breaking the merge logic which requires smallest element first.

3. Final Answer:

   Comparator reverses order, creating max heap instead of min heap -> Option C

4. Quick Check:

   Comparator direction = min heap needed [OK]

Hint: Comparator must order ascending for min heap [OK]

Common Mistakes:

• Using (b[0] - a[0]) instead of (a[0] - b[0])
• Ignoring empty list checks
• Not incrementing elementIndex properly

5. Given K sorted linked lists, which approach best optimizes the time complexity when merging them using a min heap? A) Insert all elements from all lists into a min heap and then extract all. B) Insert only the first element of each list into the min heap and then insert next elements as you extract. C) Merge lists two at a time repeatedly without using a heap. D) Use a max heap to store all elements and then reverse the result.

hard

A. Insert first elements only, add next after extraction

B. Insert all elements at once into min heap

C. Merge lists pairwise without heap

D. Use max heap and reverse output

Solution

1. Step 1: Compare time complexities of approaches

   Inserting all elements at once (A) costs O(N log N) where N is total elements. Pairwise merging (C) costs more. Using max heap and reversing (D) is inefficient.

2. Step 2: Explain min heap incremental insertion (B)

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

3. Final Answer:

   Insert first elements only, add next after extraction -> Option A

4. Quick Check:

   Optimal merge = incremental min heap insertion [OK]

Hint: Keep heap size K by adding next elements after polling [OK]

Common Mistakes:

• Inserting all elements at once causing slow performance
• Using max heap incorrectly
• Ignoring heap size impact on complexity