Merge K Sorted Lists Using Min Heap in DSA C

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 their own sorted book. You want to write down all the pages in order. You ask each friend for their current page, pick the smallest page number, write it down, then ask that friend for their next page. The min heap helps you quickly find the smallest page among all friends.

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

Min Heap (stores current heads):
[1, 2, 3]
↑ min element at root

Dry Run Walkthrough

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

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

Step 1: Build min heap with first nodes of all lists: 1, 2, 3

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, add to merged list, push next node (4) from List1 into heap

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

Why: We add smallest element to result and replace it with next from same list

Step 3: Extract min (2), add to merged list, push next node (5) from List2

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

Why: Continue picking smallest and replenishing heap

Step 4: Extract min (3), add to merged list, push next node (6) from List3

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

Why: Keep merging by always choosing smallest current node

Step 5: Extract min (4), add to merged list, push next node (7) from List1

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

Why: Replace extracted node with next from same list

Step 6: Extract min (5), add to merged list, push next node (8) from List2

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

Why: Continue until all nodes are merged

Step 7: Extract min (6), add to merged list, push next node (9) from List3

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

Why: Keep heap updated with next nodes

Step 8: Extract min (7), add to merged list, List1 has no more nodes, so do not push

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

Why: When a list ends, just remove its node from heap

Step 9: Extract min (8), 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 heap is empty

Step 10: Extract min (9), 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 means done

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Definition for singly-linked list.
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// Min heap node stores pointer to list node
typedef struct {
    ListNode **arr;
    int size;
    int capacity;
} MinHeap;

MinHeap* createMinHeap(int capacity) {
    MinHeap *heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->arr = (ListNode**)malloc(sizeof(ListNode*) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void swap(ListNode **a, ListNode **b) {
    ListNode *temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyDown(MinHeap *heap, int i) {
    int smallest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < heap->size && heap->arr[left]->val < heap->arr[smallest]->val)
        smallest = left;
    if (right < heap->size && heap->arr[right]->val < heap->arr[smallest]->val)
        smallest = right;

    if (smallest != i) {
        swap(&heap->arr[i], &heap->arr[smallest]);
        heapifyDown(heap, smallest); // maintain heap property
    }
}

void heapifyUp(MinHeap *heap, int i) {
    int parent = (i - 1) / 2;
    if (i && heap->arr[i]->val < heap->arr[parent]->val) {
        swap(&heap->arr[i], &heap->arr[parent]);
        heapifyUp(heap, parent); // maintain heap property
    }
}

void insertHeap(MinHeap *heap, ListNode *node) {
    if (heap->size == heap->capacity) return; // no resize for simplicity
    heap->arr[heap->size] = node;
    heapifyUp(heap, heap->size); // restore heap
    heap->size++;
}

ListNode* extractMin(MinHeap *heap) {
    if (heap->size == 0) return NULL;
    ListNode *root = heap->arr[0];
    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;
    heapifyDown(heap, 0); // restore heap
    return root;
}

ListNode* mergeKLists(ListNode** lists, int k) {
    MinHeap *heap = createMinHeap(k);
    // Insert first node of each list into heap
    for (int i = 0; i < k; i++) {
        if (lists[i] != NULL) {
            insertHeap(heap, lists[i]); // add current head
        }
    }

    ListNode dummy;
    ListNode *tail = &dummy;
    dummy.next = NULL;

    while (heap->size > 0) {
        ListNode *minNode = extractMin(heap); // get smallest node
        tail->next = minNode; // add to merged list
        tail = tail->next;
        if (minNode->next != NULL) {
            insertHeap(heap, minNode->next); // add next node from same list
        }
    }
    tail->next = NULL;
    free(heap->arr);
    free(heap);
    return dummy.next;
}

// Helper to create list from array
ListNode* createList(int *arr, int n) {
    ListNode dummy;
    ListNode *tail = &dummy;
    dummy.next = NULL;
    for (int i = 0; i < n; i++) {
        ListNode *node = (ListNode*)malloc(sizeof(ListNode));
        node->val = arr[i];
        node->next = NULL;
        tail->next = node;
        tail = node;
    }
    return dummy.next;
}

// Helper to print list
void printList(ListNode *head) {
    while (head != NULL) {
        printf("%d", head->val);
        if (head->next != NULL) printf(" -> ");
        head = head->next;
    }
    printf(" -> null\n");
}

int main() {
    int arr1[] = {1, 4, 7};
    int arr2[] = {2, 5, 8};
    int arr3[] = {3, 6, 9};

    ListNode *list1 = createList(arr1, 3);
    ListNode *list2 = createList(arr2, 3);
    ListNode *list3 = createList(arr3, 3);

    ListNode *lists[] = {list1, list2, list3};

    ListNode *merged = mergeKLists(lists, 3);
    printList(merged);

    return 0;
}

for (int i = 0; i < k; i++) { if (lists[i] != NULL) { insertHeap(heap, lists[i]); // add current head } }

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

while (heap->size > 0) { ListNode *minNode = extractMin(heap); // get smallest node tail->next = minNode; // add to merged list tail = tail->next; if (minNode->next != NULL) { insertHeap(heap, minNode->next); // add next node from same list } }

Repeatedly extract smallest node, add to result, and insert next node from that 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 min heap storing one node from each list at a time

vs Alternative: Naive merging by repeated merging two lists at a time takes O(kN) which is slower when k is large

Edge Cases

All input lists are empty

The merged list is empty (null) because heap never gets nodes

DSA C

if (lists[i] != NULL) { insertHeap(heap, lists[i]); }

Some lists are empty, others have nodes

Only non-empty lists contribute nodes to merged list

DSA C

if (lists[i] != NULL) { insertHeap(heap, lists[i]); }

Lists contain duplicate values

Duplicates are merged in sorted order correctly because heap compares node values

DSA C

if (heap->arr[left]->val < heap->arr[smallest]->val)

When to Use This Pattern

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

Common Mistakes

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

Mistake: Building the heap with all nodes at once instead of only the first nodes
Fix: Initialize heap with only the first node of each list to keep heap size small

Summary

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

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

The key is to keep only the current smallest nodes from each list in a min heap to always pick the next smallest element.

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 all lists at each step.

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 without sorting.

Solution

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

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

2. Step 2: Compare options based on heap usage

   Only It efficiently finds the smallest element among all lists at each step. correctly states the advantage of min heap in efficiently finding the smallest element at each step.

3. Final Answer:

   It efficiently finds the smallest element among all lists at each step. -> Option A

4. Quick Check:

   Min heap = efficient smallest element retrieval [OK]

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

Common Mistakes:

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

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

easy

A. heap<int> minHeap = make_heap();

B. minHeap = new MinHeap();

C. priority_queue minHeap;

D. int minHeap[] = {};

Solution

1. Step 1: Recognize C++ STL syntax for min heap

   In C++, a min heap is created using priority_queue with greater comparator as in priority_queue minHeap;.

2. Step 2: Check other options for correctness

   minHeap = new MinHeap(); is incomplete syntax, C is invalid, and D is just an array, not a heap.

3. Final Answer:

   priority_queue minHeap; -> Option C

4. Quick Check:

   Min heap init in C++ STL = priority_queue with greater comparator [OK]

Hint: Use priority_queue with greater<int> for min heap [OK]

Common Mistakes:

• Using default priority_queue (max heap)
• Trying to create heap with invalid syntax
• Confusing array with heap structure

3. Given three sorted lists: [1,4,5], [1,3,4], and [2,6], what is the merged sorted list using a min heap?

medium

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

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

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

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

Solution

1. Step 1: Combine all elements maintaining order

   All elements from lists combined: 1,4,5; 1,3,4; 2,6.

2. Step 2: Sort combined elements

   Sorted combined list is [1,1,2,3,4,4,5,6].

3. Final Answer:

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

4. Quick Check:

   Merge sorted lists = sorted combined elements [OK]

Hint: Merge all, then sort or use min heap to pick smallest [OK]

Common Mistakes:

• Missing duplicate 1 or 4
• Skipping 2 or 3 in merged list
• Incorrect order of elements

4. What is the error in the following code snippet for merging K sorted lists using a min heap?

for (int i = 0; i < lists.size(); i++) {
    minHeap.push(lists[i][0]);
}
while (!minHeap.empty()) {
    int val = minHeap.top();
    minHeap.pop();
    result.push_back(val);
}

medium

A. It uses pop() before top(), causing runtime error.

B. It only pushes the first element of each list and never pushes next elements.

C. It does not initialize the min heap properly.

D. It pushes all elements at once, causing overflow.

Solution

1. Step 1: Analyze the push operation

   The code pushes only the first element of each list into the min heap.

2. Step 2: Check if next elements are pushed

   There is no code to push the next elements from lists after popping the smallest element.

3. Final Answer:

   It only pushes the first element of each list and never pushes next elements. -> Option B

4. Quick Check:

   Missing pushing next elements after pop = bug [OK]

Hint: Always push next element from list after popping min [OK]

Common Mistakes:

• Not pushing next elements after popping
• Popping before checking top
• Incorrect heap initialization

5. You have K sorted linked lists of varying lengths. Which approach best optimizes merging them using a min heap to achieve O(N log K) time complexity, where N is total elements?

hard

A. Push the first node of each list into the min heap, then repeatedly pop the smallest and push its next node until all nodes are processed.

B. Concatenate all lists into one and then sort the combined list using quicksort.

C. Push all nodes from all lists into the min heap at once, then pop all to get sorted order.

D. Merge lists two at a time using simple merge sort repeatedly until one list remains.

Solution

1. Step 1: Understand time complexity of each approach

   Push the first node of each list into the min heap, then repeatedly pop the smallest and push its next node until all nodes are processed. uses a min heap of size K, pushing and popping nodes efficiently, achieving O(N log K).

2. Step 2: Compare other options

   Concatenate all lists into one and then sort the combined list using quicksort. sorts all elements at once, O(N log N). Push all nodes from all lists into the min heap at once, then pop all to get sorted order. pushes all nodes at once, O(N log N). Merge lists two at a time using simple merge sort repeatedly until one list remains. merges lists pairwise, O(N log K) but less efficient than min heap approach.

3. Final Answer:

   Push the first node of each list into the min heap, then repeatedly pop the smallest and push its next node until all nodes are processed. -> Option A

4. Quick Check:

   Min heap with K nodes = O(N log K) merge [OK]

Hint: Push first nodes, pop min, push next nodes for O(N log K) [OK]

Common Mistakes:

• Pushing all nodes at once causing O(N log N)
• Using pairwise merges inefficiently
• Sorting concatenated list instead of merging