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

Merge K Sorted Lists Using Min Heap

📖 Scenario: Imagine you have multiple sorted lists of numbers, like sorted queues of people waiting in line. You want to combine all these lines into one big sorted line efficiently.

🎯 Goal: Build a Java 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 an array of integer arrays representing the sorted lists

Use a variable to track the number of lists k

Use a min heap (Java PriorityQueue) to merge the lists efficiently

Print the final merged sorted list as output

💡 Why This Matters

🌍 Real World

Merging sorted lists is useful in scenarios like combining sorted data from multiple sources, such as merging search results or logs.

💼 Career

Understanding how to merge sorted data efficiently is important for software engineers working with databases, big data, and real-time data processing.

1

Create the sorted lists data

Create an array of integer arrays called sortedLists with these exact lists: {1, 4, 7}, {2, 5, 8}, and {3, 6, 9}.

DSA Java

# Create the array of sorted integer arrays called sortedLists
# Your code here

Hint

Use int[][] sortedLists = { ... }; to create the array of arrays.

2

Set the number of lists

Create an integer variable called k and set it to the length of sortedLists.

DSA Java

int[][] sortedLists = {
    {1, 4, 7},
    {2, 5, 8},
    {3, 6, 9}
};

// Create variable k for number of lists
# Your code here

Hint

Use int k = sortedLists.length; to get the number of lists.

3

Merge the lists using a min heap

Write code to merge the k sorted lists using a PriorityQueue of a helper class Node that stores the value, list index, and element index. Initialize the queue with the first element of each list. Then repeatedly poll the smallest element, add it to a result list, and add the next element from the same list to the queue if available.

DSA Java

import java.util.*;

int[][] sortedLists = {
    {1, 4, 7},
    {2, 5, 8},
    {3, 6, 9}
};

int k = sortedLists.length;

// Define Node class and merge logic below
# Your code here

Hint

Use a PriorityQueue and a Node class with compareTo to keep the smallest element on top.

4

Print the merged sorted list

Print the mergedList using System.out.println(mergedList); to show the final merged sorted list.

DSA Java

import java.util.*;

int[][] sortedLists = {
    {1, 4, 7},
    {2, 5, 8},
    {3, 6, 9}
};

int k = sortedLists.length;

class Node implements Comparable {
    int value;
    int listIndex;
    int elementIndex;

    Node(int value, int listIndex, int elementIndex) {
        this.value = value;
        this.listIndex = listIndex;
        this.elementIndex = elementIndex;
    }

    public int compareTo(Node other) {
        return this.value - other.value;
    }
}

PriorityQueue minHeap = new PriorityQueue();

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

List mergedList = new ArrayList();

while (!minHeap.isEmpty()) {
    Node current = minHeap.poll();
    mergedList.add(current.value);
    int nextIndex = current.elementIndex + 1;
    if (nextIndex < sortedLists[current.listIndex].length) {
        minHeap.add(new Node(sortedLists[current.listIndex][nextIndex], current.listIndex, nextIndex));
    }
}

// Print the merged list
# Your code here

Hint

Use System.out.println(mergedList); to print the final merged 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