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

Merge K Sorted Lists Using Min Heap

📖 Scenario: Imagine you have multiple sorted lists of numbers from different sources, like scores from different games. You want to combine all these lists into one big sorted list quickly.

🎯 Goal: You will build a program that merges k sorted lists into one sorted list using a min heap (priority queue) to keep track of the smallest elements efficiently.

📋 What You'll Learn

Create an array called lists containing exactly these sorted arrays: [1, 4, 5], [1, 3, 4], [2, 6]

Create a variable called minHeap to help pick the smallest element from the lists

Write the core logic to merge all lists into one sorted array called mergedList

Print the mergedList array as the final output

💡 Why This Matters

🌍 Real World

Merging sorted data streams from multiple sources, like combining logs or sorted records.

💼 Career

Understanding heaps and merging algorithms is useful for software engineers working on databases, search engines, and real-time data processing.

1

Create the sorted lists

Create an array called lists with these exact sorted arrays: [1, 4, 5], [1, 3, 4], and [2, 6]

DSA Javascript

# Your code here

Hint

Use const lists = [[1, 4, 5], [1, 3, 4], [2, 6]]; to create the array of sorted lists.

2

Set up the min heap array

Create an empty array called minHeap to use as a helper structure for merging the lists

DSA Javascript

const lists = [[1, 4, 5], [1, 3, 4], [2, 6]];
// Create an empty array called minHeap
# Your code here

Hint

Use const minHeap = []; to create an empty array for the min heap.

3

Write the core logic to merge lists using the min heap

Write code to merge the sorted lists into one sorted array called mergedList using the minHeap array as a helper. Use a loop to add the first element of each list to minHeap, then repeatedly extract the smallest element and add the next element from the same list until all elements are merged.

DSA Javascript

const lists = [[1, 4, 5], [1, 3, 4], [2, 6]];
const minHeap = [];
// Write the merging logic here
# Your code here

Hint

Use a min heap to always pick the smallest current element from the lists. Insert the first element of each list into the heap, then repeatedly extract the smallest and add the next element from the same list.

4

Print the merged sorted list

Print the mergedList array to show the final merged sorted list

DSA Javascript

const lists = [[1, 4, 5], [1, 3, 4], [2, 6]];
const minHeap = [];

// Helper function to swap elements in the heap
function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// Heapify up to maintain min heap property
function heapifyUp(heap, index) {
    while (index > 0) {
        const parent = Math.floor((index - 1) / 2);
        if (heap[parent][0]  0) {
        heap[0] = last;
        heapifyDown(heap, 0);
    }
    return min;
}

const mergedList = [];

// Initialize minHeap with first element of each list along with list index and element index
for (let i = 0; i  0) {
        insert(minHeap, [lists[i][0], i, 0]);
    }
}

// Extract min and add next element from same list until heap is empty
while (minHeap.length > 0) {
    const [value, listIndex, elementIndex] = extractMin(minHeap);
    mergedList.push(value);
    const nextIndex = elementIndex + 1;
    if (nextIndex < lists[listIndex].length) {
        insert(minHeap, [lists[listIndex][nextIndex], listIndex, nextIndex]);
    }
}

// Print the mergedList
console.log(mergedList);

Hint

Use console.log(mergedList); to print the final merged sorted list.

Practice

1. What is the main purpose of using a min heap when merging K sorted lists?

easy

A. To sort each individual list before merging

B. To efficiently find the smallest element among the heads of all lists

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 candidates, which is essential when merging sorted lists.

2. Step 2: Apply this to merging K sorted lists

   By pushing the first element of each list into the min heap, we can always extract the smallest element efficiently to build the merged list.

3. Final Answer:

   To efficiently find the smallest element among the heads of all lists -> Option B

4. Quick Check:

   Min heap = smallest element finder [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 min heap with max heap

2. Which of the following is the correct way to insert an element into a min heap in JavaScript?

easy

A. heap.push(element); heapifyUp();

B. heap.pop(); heapifyDown();

C. heap.unshift(element); heapifyDown();

D. heap.shift(); heapifyUp();

Solution

1. Step 1: Understand insertion in min heap

   To insert, add the element at the end (push), then move it up to maintain heap property (heapifyUp).

2. Step 2: Match with options

   heap.push(element); heapifyUp(); correctly shows push followed by heapifyUp, which is the standard insertion method.

3. Final Answer:

   heap.push(element); heapifyUp(); -> Option A

4. Quick Check:

   Insert = push + heapifyUp [OK]

Hint: Insert by push then heapify up [OK]

Common Mistakes:

• Using pop or shift to insert
• Calling heapifyDown after insertion
• Using unshift which is inefficient

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

const lists = [[1,4,5],[1,3,4],[2,6]];
function mergeKLists(lists) {
  const minHeap = [];
  const result = [];
  for (let i = 0; i < lists.length; i++) {
    if (lists[i].length > 0) minHeap.push({ val: lists[i][0], listIndex: i, elementIndex: 0 });
  }
  minHeap.sort((a,b) => a.val - b.val);
  while (minHeap.length > 0) {
    const smallest = minHeap.shift();
    result.push(smallest.val);
    const nextIndex = smallest.elementIndex + 1;
    if (nextIndex < lists[smallest.listIndex].length) {
      minHeap.push({ val: lists[smallest.listIndex][nextIndex], listIndex: smallest.listIndex, elementIndex: nextIndex });
      minHeap.sort((a,b) => a.val - b.val);
    }
  }
  return result;
}
console.log(mergeKLists(lists));

medium

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

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

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

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

Solution

1. Step 1: Initialize min heap with first elements

   minHeap starts with {1,0,0}, {1,1,0}, {2,2,0} sorted as [1,1,2].

2. Step 2: Extract smallest and add next elements

   Extract 1 from list 0, add 4; extract 1 from list 1, add 3; extract 2 from list 2, add 6; continue until all elements merged.

3. Final Answer:

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

4. Quick Check:

   Merged sorted list = [1,1,2,3,4,4,5,6] [OK]

Hint: Track smallest and add next from same list [OK]

Common Mistakes:

• Not sorting minHeap after each insertion
• Forgetting to add next element from same list
• Returning concatenated lists instead of merged

4. Identify the bug in the following code snippet for merging K sorted lists using a min heap:

function mergeKLists(lists) {
  const minHeap = [];
  const result = [];
  for (let i = 0; i < lists.length; i++) {
    minHeap.push({ val: lists[i][0], listIndex: i, elementIndex: 0 });
  }
  minHeap.sort((a,b) => a.val - b.val);
  while (minHeap.length > 0) {
    const smallest = minHeap.shift();
    result.push(smallest.val);
    const nextIndex = smallest.elementIndex + 1;
    if (nextIndex < lists[smallest.listIndex].length) {
      minHeap.push({ val: lists[smallest.listIndex][nextIndex], listIndex: smallest.listIndex, elementIndex: nextIndex });
      minHeap.sort((a,b) => a.val - b.val);
    }
  }
  return result;
}

medium

A. Not initializing minHeap with first elements of lists

B. Not pushing the first element of each list into minHeap

C. Using shift() instead of pop() to get smallest element

D. Missing sorting minHeap after pushing new element inside the loop

Solution

1. Step 1: Check minHeap maintenance inside loop

   After pushing a new element, minHeap must be sorted to keep smallest element at front.

2. Step 2: Identify missing sorting

   The code pushes new elements but does not sort minHeap again, breaking the min heap property.

3. Final Answer:

   Missing sorting minHeap after pushing new element inside the loop -> Option D

4. Quick Check:

   Sort after push to maintain min heap [OK]

Hint: Always re-sort min heap after insertion [OK]

Common Mistakes:

• Forgetting to sort minHeap after push
• Confusing shift() and pop() usage
• Not pushing initial elements into minHeap

5. Given K sorted linked lists, which approach best optimizes the time complexity when merging them using a min heap?

hard

A. Insert only the first element of each list into the min heap, then extract and insert next elements dynamically

B. Insert all elements from all lists into the min heap at once, then extract all

C. Merge lists two at a time without using a min heap

D. Concatenate all lists and sort the combined list

Solution

1. Step 1: Analyze time complexity of inserting all elements at once

   Inserting all elements at once leads to O(N log N) where N is total elements, which is less efficient.

2. Step 2: Understand dynamic insertion approach

   Inserting only first elements and dynamically adding next elements keeps heap size at K, leading to O(N log K) time, which is optimal.

3. Final Answer:

   Insert only the first element of each list into the min heap, then extract and insert next elements dynamically -> Option A

4. Quick Check:

   Dynamic insertion = O(N log K) best [OK]

Hint: Keep heap size small by dynamic insertion [OK]

Common Mistakes:

• Inserting all elements at once causing slow performance
• Ignoring heap size impact on complexity
• Using simple concatenation and sort which is inefficient