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

Merge K Sorted Lists Using Min Heap

📖 Scenario: Imagine you have multiple sorted lists of numbers from different sources, like sorted lists of daily temperatures from different cities. You want to combine all these lists into one big sorted list efficiently.

🎯 Goal: Build a program that merges k sorted lists into one sorted list using a min heap (priority queue) to always pick the smallest next number.

📋 What You'll Learn

Create a list of integer arrays representing the sorted lists

Use a min heap (priority queue) to efficiently find the smallest element among the lists

Merge all lists into one sorted list

Print the merged sorted list

💡 Why This Matters

🌍 Real World

Merging sorted data streams from multiple sources is common in databases, search engines, and real-time data processing.

💼 Career

Understanding how to merge sorted lists efficiently is important for software engineers working with large datasets, optimizing performance, and building scalable systems.

1

Create the sorted lists data

Create a variable called sortedLists that is a List<int[]> containing these exact arrays: new int[] {1, 4, 7}, new int[] {2, 5, 8}, and new int[] {3, 6, 9}.

DSA C#

# Create the sortedLists variable with the given arrays
# Your code here

Hint

Use List<int[]> and initialize it with the three arrays exactly as shown.

2

Set up the min heap and helper class

Create a class called HeapNode with public integer fields Value, ListIndex, and ElementIndex. Then, create a PriorityQueue<HeapNode, int> called minHeap inside Main.

DSA C#

using System;
using System.Collections.Generic;

class HeapNode
{
    // Define Value, ListIndex, ElementIndex fields here
}

class Program
{
    static void Main()
    {
        List sortedLists = new List
        {
            new int[] {1, 4, 7},
            new int[] {2, 5, 8},
            new int[] {3, 6, 9}
        };

        // Create minHeap here
        # Your code here
    }
}

Hint

Define the HeapNode class with the three fields and a constructor. Then create minHeap as a PriorityQueue<HeapNode, int>.

3

Add first elements to the min heap and merge lists

Add the first element of each array in sortedLists to minHeap as HeapNode objects. Then, create a List<int> called mergedList. Use a while loop to remove the smallest element from minHeap, add its value to mergedList, and if the next element exists in the same list, add that next element as a new HeapNode to minHeap.

DSA C#

using System;
using System.Collections.Generic;

class HeapNode
{
    public int Value;
    public int ListIndex;
    public int ElementIndex;

    public HeapNode(int value, int listIndex, int elementIndex)
    {
        Value = value;
        ListIndex = listIndex;
        ElementIndex = elementIndex;
    }
}

class Program
{
    static void Main()
    {
        List sortedLists = new List
        {
            new int[] {1, 4, 7},
            new int[] {2, 5, 8},
            new int[] {3, 6, 9}
        };

        PriorityQueue minHeap = new PriorityQueue();

        // Add first elements of each list to minHeap
        // Create mergedList
        // Use while loop to merge all lists
        # Your code here
    }
}

Hint

Loop through each list to add the first element to the heap. Then repeatedly remove the smallest element, add it to mergedList, and add the next element from the same list if available.

4

Print the merged sorted list

Print the contents of mergedList as a single line of numbers separated by spaces using Console.WriteLine.

DSA C#

using System;
using System.Collections.Generic;

class HeapNode
{
    public int Value;
    public int ListIndex;
    public int ElementIndex;

    public HeapNode(int value, int listIndex, int elementIndex)
    {
        Value = value;
        ListIndex = listIndex;
        ElementIndex = elementIndex;
    }
}

class Program
{
    static void Main()
    {
        List sortedLists = new List
        {
            new int[] {1, 4, 7},
            new int[] {2, 5, 8},
            new int[] {3, 6, 9}
        };

        PriorityQueue minHeap = new PriorityQueue();

        for (int i = 0; i  0)
            {
                minHeap.Enqueue(new HeapNode(sortedLists[i][0], i, 0), sortedLists[i][0]);
            }
        }

        List mergedList = new List();

        while (minHeap.Count > 0)
        {
            HeapNode current = minHeap.Dequeue();
            mergedList.Add(current.Value);

            int nextIndex = current.ElementIndex + 1;
            if (nextIndex < sortedLists[current.ListIndex].Length)
            {
                int nextValue = sortedLists[current.ListIndex][nextIndex];
                minHeap.Enqueue(new HeapNode(nextValue, current.ListIndex, nextIndex), nextValue);
            }
        }

        // Print mergedList as space-separated numbers
        # Your code here
    }
}

Hint

Use Console.WriteLine(string.Join(" ", mergedList)) to print all numbers separated by spaces.

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