Merge K Sorted Lists Using Min Heap in DSA C - Build from Scratch

Merge K Sorted Lists Using Min Heap

📋 What You'll Learn

💡 Why This Matters

🌍 Real World

Merging sorted data streams from multiple sources efficiently is common in databases, log processing, and real-time analytics.

💼 Career

Understanding how to merge multiple sorted lists using a min heap is useful for software engineers working on data processing, backend systems, and performance optimization.

1

Create 3 sorted linked lists

Create three sorted linked lists named list1, list2, and list3 with these exact values:
list1: 1 -> 4 -> 7 -> NULL
list2: 2 -> 5 -> 8 -> NULL
list3: 3 -> 6 -> 9 -> NULL
Use the struct Node with int data and struct Node *next.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node *next;
};

// Helper function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

int main() {
    // Create list1 with nodes 1 -> 4 -> 7 -> NULL
    // Create list2 with nodes 2 -> 5 -> 8 -> NULL
    // Create list3 with nodes 3 -> 6 -> 9 -> NULL
    // Your code here

    return 0;
}

Hint

Use the newNode function to create each node and link them using the next pointer.

2

Create an array of list heads and a variable for number of lists

Create an array of struct Node* named lists containing list1, list2, and list3. Also create an integer variable k and set it to 3.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node *next;
};

// Helper function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

int main() {
    struct Node* list1 = newNode(1);
    list1->next = newNode(4);
    list1->next->next = newNode(7);

    struct Node* list2 = newNode(2);
    list2->next = newNode(5);
    list2->next->next = newNode(8);

    struct Node* list3 = newNode(3);
    list3->next = newNode(6);
    list3->next->next = newNode(9);

    // Create array lists containing list1, list2, list3
    // Create integer k and set it to 3
    // Your code here

    return 0;
}

Hint

Use an array to hold the pointers to the heads of the lists and set k to 3.

3

Implement mergeKLists function using min heap

Implement a function struct Node* mergeKLists(struct Node* lists[], int k) that merges the k sorted linked lists using a min heap. Use a min heap to always pick the smallest node among the current heads of the lists. Return the head of the merged sorted linked list.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node *next;
};

// Helper function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Function to merge k sorted linked lists using min heap
struct Node* mergeKLists(struct Node* lists[], int k) {
    // Implement min heap to merge lists
    // Your code here
}

int main() {
    struct Node* list1 = newNode(1);
    list1->next = newNode(4);
    list1->next->next = newNode(7);

    struct Node* list2 = newNode(2);
    list2->next = newNode(5);
    list2->next->next = newNode(8);

    struct Node* list3 = newNode(3);
    list3->next = newNode(6);
    list3->next->next = newNode(9);

    struct Node* lists[3] = {list1, list2, list3};
    int k = 3;

    struct Node* mergedHead = mergeKLists(lists, k);

    return 0;
}

Hint

Use a min heap to keep track of the smallest current nodes from each list. Extract the smallest, add it to the merged list, and if that node has a next, add it back to the heap.

4

Print the merged linked list

Write a printList function that prints the merged linked list nodes separated by -> and ending with NULL. Then call printList(mergedHead) in main to display the merged list.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node *next;
};

// Helper function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Min heap node structure
struct HeapNode {
    struct Node* node;
};

// Swap two heap nodes
void swap(struct HeapNode* a, struct HeapNode* b) {
    struct HeapNode temp = *a;
    *a = *b;
    *b = temp;
}

// Min heapify function
void minHeapify(struct HeapNode heap[], int size, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left data data)
        smallest = left;
    if (right data data)
        smallest = right;

    if (smallest != i) {
        swap(&heap[i], &heap[smallest]);
        minHeapify(heap, size, smallest);
    }
}

// Build min heap
void buildMinHeap(struct HeapNode heap[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        minHeapify(heap, size, i);
    }
}

// Extract min node from heap
struct Node* extractMin(struct HeapNode heap[], int* size) {
    if (*size == 0) return NULL;
    struct Node* root = heap[0].node;
    if (root->next) {
        heap[0].node = root->next;
    } else {
        heap[0] = heap[*size - 1];
        (*size)--;
    }
    minHeapify(heap, *size, 0);
    return root;
}

// Merge k sorted linked lists using min heap
struct Node* mergeKLists(struct Node* lists[], int k) {
    struct HeapNode* heap = (struct HeapNode*)malloc(k * sizeof(struct HeapNode));
    int heapSize = 0;

    // Initialize heap with first node of each list if not NULL
    for (int i = 0; i  0) {
        struct Node* minNode = extractMin(heap, &heapSize);
        tail->next = minNode;
        tail = tail->next;
    }

    free(heap);
    return dummy.next;
}

// Your code here

int main() {
    struct Node* list1 = newNode(1);
    list1->next = newNode(4);
    list1->next->next = newNode(7);

    struct Node* list2 = newNode(2);
    list2->next = newNode(5);
    list2->next->next = newNode(8);

    struct Node* list3 = newNode(3);
    list3->next = newNode(6);
    list3->next->next = newNode(9);

    struct Node* lists[3] = {list1, list2, list3};
    int k = 3;

    struct Node* mergedHead = mergeKLists(lists, k);

    // Print the merged list
    // Your code here

    return 0;
}

Hint

Traverse the merged linked list and print each node's data followed by ->. End with NULL.

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