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.