Merge K Sorted Lists Using Min Heap in DSA Python

Mental Model

We combine many sorted lists into one sorted list by always picking the smallest next item from all lists using a small helper structure.

Analogy: Imagine you have K friends each reading their own sorted book aloud. You want to write down all the words in order. You listen to the smallest next word among all friends and write it down, then ask that friend for their next word.

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

MinHeap: [1, 2, 3]
Output: null

Dry Run Walkthrough

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

Goal: Merge all 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]
Output: null

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

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

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

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

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

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

Why: Continue picking smallest and replenishing heap from lists

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

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

Why: Keep merging by always choosing smallest next element

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

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

Why: Process continues until all nodes are merged

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

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

Why: Heap always holds next smallest candidates

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

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

Why: Continue merging until heap is empty

Step 8: Extract min (7) from heap and add to output; list1 exhausted, no insertion

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

Why: No more nodes in list1, heap shrinks

Step 9: Extract min (8) from heap and add to output; list2 exhausted, no insertion

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

Why: No more nodes in list2

Step 10: Extract min (9) from heap and add to output; list3 exhausted, no insertion

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

Why: All lists merged, heap empty

Result:

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

Annotated Code

DSA Python

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        return str(self.val)

def merge_k_lists(lists):
    min_heap = []
    # Push first node of each list into heap
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(min_heap, (node.val, i, node))

    dummy = ListNode(0)
    current = dummy

    while min_heap:
        val, i, node = heapq.heappop(min_heap)  # Extract smallest node
        current.next = node  # Add it to merged list
        current = current.next
        if node.next:
            heapq.heappush(min_heap, (node.next.val, i, node.next))  # Push next node from same list

    return dummy.next

def print_list(node):
    result = []
    while node:
        result.append(str(node.val))
        node = node.next
    print(' -> '.join(result) + ' -> null')

# Driver code using dry_run input
list1 = ListNode(1, ListNode(4, ListNode(7)))
list2 = ListNode(2, ListNode(5, ListNode(8)))
list3 = ListNode(3, ListNode(6, ListNode(9)))
lists = [list1, list2, list3]
merged = merge_k_lists(lists)
print_list(merged)

for i, node in enumerate(lists): if node: heapq.heappush(min_heap, (node.val, i, node))

Insert first node of each list into min heap to start merging

val, i, node = heapq.heappop(min_heap)

Extract smallest node from heap to add to merged list

current.next = node current = current.next

Append extracted node to merged list and move current pointer

if node.next: heapq.heappush(min_heap, (node.next.val, i, node.next))

If extracted node has next, push it into heap to continue merging

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 costs O(log K) where K is number of lists

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

vs Alternative: Naive merging by repeated two-list merges costs O(KN) which is slower; min heap approach is more efficient for large K

Edge Cases

Empty list of lists

Returns null immediately, no merging needed

DSA Python

for i, node in enumerate(lists):
    if node:

Some lists are empty

Only non-empty lists contribute nodes to heap and merged list

DSA Python

if node:

All lists empty

Returns null as no nodes to merge

DSA Python

for i, node in enumerate(lists):
    if node:

When to Use This Pattern

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

Common Mistakes

Mistake: Not pushing the next node of the extracted node back into the heap
Fix: After popping from heap, always check and push the next node from the same list if it exists

Mistake: Using a heap without storing list index to break ties
Fix: Include list index in heap tuple to avoid comparison errors when node values are equal

Summary

Merges K sorted linked lists into one sorted list using a min heap to efficiently pick the smallest next node.

Use when you have multiple sorted lists and want to merge them with good performance.

The key is to keep only the next smallest candidates in a min heap, so you always pick the smallest next node quickly.

Practice

1. What is the main advantage of using a min heap to merge k sorted lists?

easy

A. It efficiently finds the smallest element among the heads of all lists.

B. It sorts each individual list before merging.

C. It uses extra space to store all elements at once.

D. It merges lists by concatenating them directly.

Solution

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

   A min heap helps keep track of the smallest element among multiple sorted lists efficiently.

2. Step 2: Compare with other options

   Options B, C, and D do not describe the min heap's main advantage in this context.

3. Final Answer:

   It efficiently finds the smallest element among the heads of all lists. -> Option A

4. Quick Check:

   Min heap = smallest element tracking [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 concatenation with merging

2. Which of the following Python code snippets correctly initializes a min heap with the first elements of each sorted list named lists?

easy

A. heap = [lst[0] for lst in lists if lst]; import heapq; heapq.heapify(heap)

B. heap = lists[0]; import heapq; heapq.heapify(heap)

C. heap = []; for lst in lists: heap.append(lst); import heapq; heapq.heapify(heap)

D. heap = lists; import heapq; heapq.heapify(heap)

Solution

1. Step 1: Extract first elements safely

   heap = [lst[0] for lst in lists if lst]; import heapq; heapq.heapify(heap) uses list comprehension to get first elements only if the list is not empty.

2. Step 2: Check heap initialization

   heap = [lst[0] for lst in lists if lst]; import heapq; heapq.heapify(heap) then calls heapq.heapify to create a min heap from these elements correctly.

3. Final Answer:

   heap = [lst[0] for lst in lists if lst]; import heapq; heapq.heapify(heap) -> Option A

4. Quick Check:

   Correct min heap initialization = heap = [lst[0] for lst in lists if lst]; import heapq; heapq.heapify(heap) [OK]

Hint: Use list comprehension with condition and heapq.heapify [OK]

Common Mistakes:

• Not checking if list is empty before accessing lst[0]
• Heapifying entire lists instead of first elements
• Assigning heap to a single list instead of elements

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

import heapq
lists = [[1,4,5],[1,3,4],[2,6]]
heap = []
for i, lst in enumerate(lists):
    if lst:
        heapq.heappush(heap, (lst[0], i, 0))
result = []
while heap:
    val, list_idx, element_idx = heapq.heappop(heap)
    result.append(val)
    if element_idx + 1 < len(lists[list_idx]):
        next_tuple = (lists[list_idx][element_idx+1], list_idx, element_idx+1)
        heapq.heappush(heap, next_tuple)
print(result)

medium

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

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

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

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

Solution

1. Step 1: Trace heap operations

   Initially, heap contains (1,0,0), (1,1,0), (2,2,0). We pop smallest 1, add next element 4 from list 0, then pop next 1, add 3 from list 1, and so on.

2. Step 2: Build merged list step-by-step

   Result builds as [1,1,2,3,4,4,5,6] by always popping smallest and pushing next from same 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: Track heap pops and pushes carefully [OK]

Common Mistakes:

• Missing duplicate 1s in output
• Forgetting to push next element from same list
• Adding elements out of order

4. Identify the error in the following code snippet that attempts to merge k sorted lists using a min heap:

import heapq
lists = [[1,3,5],[2,4,6],[0,7,8]]
heap = []
for lst in lists:
    heapq.heappush(heap, lst[0])
result = []
while heap:
    val = heapq.heappop(heap)
    result.append(val)
print(result)

medium

A. The lists variable is not defined.

B. The heap is not initialized using heapq.heapify().

C. The code pushes only first elements and never pushes next elements from lists.

D. The code uses heappop instead of pop.

Solution

1. Step 1: Analyze heap push operations

   The code pushes only the first element of each list into the heap once and never pushes subsequent elements.

2. Step 2: Understand why this causes incomplete merge

   Without pushing next elements, only first elements are merged, so the result is incomplete and incorrect.

3. Final Answer:

   The code pushes only first elements and never pushes next elements from lists. -> Option C

4. Quick Check:

   Missing next elements push = The code pushes only first elements and never pushes next elements from lists. [OK]

Hint: Always push next elements after popping from heap [OK]

Common Mistakes:

• Assuming heapq.heapify is mandatory here
• Confusing heappop with pop
• Ignoring the need to push next elements

5. Given k sorted linked lists, which approach best describes how to merge them efficiently using a min heap? A) Insert all nodes from all lists into a min heap, then pop all to form merged list. B) Push only the first node of each list into the min heap, then repeatedly pop the smallest node and push its next node until all nodes are merged. C) Merge lists two at a time using simple merge, then merge results. D) Concatenate all lists and sort the combined list.

hard

A. Insert all nodes at once into min heap and pop all.

B. Push first nodes, pop smallest, push next nodes repeatedly.

C. Merge lists two at a time without heap.

D. Concatenate all lists and sort at the end.

Solution

1. Step 1: Understand efficient min heap usage

   Pushing only the first node of each list keeps the heap small and efficient.

2. Step 2: Describe the merging process

   Pop smallest node, add it to merged list, then push the next node from that list to heap, repeating until done.

3. Step 3: Compare with other options

   Insert all nodes at once into min heap and pop all. wastes space and time by pushing all nodes at once. Options B and D do not use min heap.

4. Final Answer:

   Push first nodes, pop smallest, push next nodes repeatedly. -> Option B

5. Quick Check:

   Efficient merge = push first nodes, pop smallest, push next [OK]

Hint: Push first nodes only, then push next after popping [OK]

Common Mistakes:

• Pushing all nodes at once wastes memory
• Not pushing next nodes after popping
• Using simple merge instead of heap for k lists