Merge K Sorted Lists Using Min Heap in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging 3 sorted lists using min heap

What is the printed merged list after running the following code that merges 3 sorted linked lists using a min heap?

DSA Javascript

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeKLists(lists) {
  const minHeap = [];

  function heapPush(node) {
    minHeap.push(node);
    let i = minHeap.length - 1;
    while (i > 0) {
      let parent = Math.floor((i - 1) / 2);
      if (minHeap[parent].val <= minHeap[i].val) break;
      [minHeap[parent], minHeap[i]] = [minHeap[i], minHeap[parent]];
      i = parent;
    }
  }

  function heapPop() {
    const top = minHeap[0];
    const last = minHeap.pop();
    if (minHeap.length === 0) return top;
    minHeap[0] = last;
    let i = 0;
    while (true) {
      let left = 2 * i + 1;
      let right = 2 * i + 2;
      let smallest = i;
      if (left < minHeap.length && minHeap[left].val < minHeap[smallest].val) smallest = left;
      if (right < minHeap.length && minHeap[right].val < minHeap[smallest].val) smallest = right;
      if (smallest === i) break;
      [minHeap[i], minHeap[smallest]] = [minHeap[smallest], minHeap[i]];
      i = smallest;
    }
    return top;
  }

  for (const node of lists) {
    if (node) heapPush(node);
  }

  const dummy = new ListNode(0);
  let current = dummy;

  while (minHeap.length > 0) {
    let node = heapPop();
    current.next = node;
    current = current.next;
    if (node.next) heapPush(node.next);
  }

  return dummy.next;
}

// Lists:
// 1 -> 4 -> 5
// 1 -> 3 -> 4
// 2 -> 6

const l1 = new ListNode(1, new ListNode(4, new ListNode(5)));
const l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
const l3 = new ListNode(2, new ListNode(6));

const merged = mergeKLists([l1, l2, l3]);

let output = '';
let node = merged;
while (node) {
  output += node.val + ' -> ';
  node = node.next;
}
output += 'null';
console.log(output);

A 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null

B 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 -> null

C 1 -> 1 -> 3 -> 4 -> 4 -> 5 -> 6 -> null

D 2 -> 6 -> 1 -> 3 -> 4 -> 4 -> 5 -> null

💡 Hint

Think about how the min heap always picks the smallest node among the heads of the lists.

The min heap always extracts the smallest node among the current heads of the k lists. The merged list is sorted and contains all nodes from all lists in ascending order.

🧠 Conceptual

intermediate

Minimum number of elements in min heap during merge

During the process of merging k sorted lists using a min heap, what is the maximum number of elements that the min heap can contain at any time?

A Sum of lengths of all lists, because all nodes are pushed at once

B k, because the heap stores the current smallest nodes from each list

C 1, because only one node is processed at a time

D k squared, because nodes are pushed multiple times

💡 Hint

Consider how many nodes are pushed into the heap initially and during the process.

The min heap contains at most one node from each list at any time, representing the current smallest unmerged node from that list. So the maximum size is k.

🔧 Debug

advanced

Identify the error in min heap push operation

What error will occur when running this min heap push function used in merging k sorted lists?

DSA Javascript

function heapPush(node) {
  minHeap.push(node);
  let i = minHeap.length - 1;
  while (i > 0) {
    let parent = Math.floor(i / 2);
    if (minHeap[parent].val <= minHeap[i].val) break;
    [minHeap[parent], minHeap[i]] = [minHeap[i], minHeap[parent]];
    i = parent;
  }
}

A TypeError because minHeap is undefined

B No error, function works correctly

C SyntaxError due to missing semicolon

D The parent index calculation is wrong, causing incorrect heap structure

💡 Hint

Check how parent index is calculated in a binary heap stored in an array.

In a zero-based array heap, parent index should be Math.floor((i - 1) / 2). Using Math.floor(i / 2) is incorrect and breaks heap property.

❓ Predict Output

advanced

Output after merging empty and non-empty lists

What is the output of merging the following lists using the min heap merge function? Lists: - null - 0 -> 2 -> 5 - null

DSA Javascript

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeKLists(lists) {
  const minHeap = [];

  function heapPush(node) {
    minHeap.push(node);
    let i = minHeap.length - 1;
    while (i > 0) {
      let parent = Math.floor((i - 1) / 2);
      if (minHeap[parent].val <= minHeap[i].val) break;
      [minHeap[parent], minHeap[i]] = [minHeap[i], minHeap[parent]];
      i = parent;
    }
  }

  function heapPop() {
    const top = minHeap[0];
    const last = minHeap.pop();
    if (minHeap.length === 0) return top;
    minHeap[0] = last;
    let i = 0;
    while (true) {
      let left = 2 * i + 1;
      let right = 2 * i + 2;
      let smallest = i;
      if (left < minHeap.length && minHeap[left].val < minHeap[smallest].val) smallest = left;
      if (right < minHeap.length && minHeap[right].val < minHeap[smallest].val) smallest = right;
      if (smallest === i) break;
      [minHeap[i], minHeap[smallest]] = [minHeap[smallest], minHeap[i]];
      i = smallest;
    }
    return top;
  }

  for (const node of lists) {
    if (node) heapPush(node);
  }

  const dummy = new ListNode(0);
  let current = dummy;

  while (minHeap.length > 0) {
    let node = heapPop();
    current.next = node;
    current = current.next;
    if (node.next) heapPush(node.next);
  }

  return dummy.next;
}

const l1 = null;
const l2 = new ListNode(0, new ListNode(2, new ListNode(5)));
const l3 = null;

const merged = mergeKLists([l1, l2, l3]);

let output = '';
let node = merged;
while (node) {
  output += node.val + ' -> ';
  node = node.next;
}
output += 'null';
console.log(output);

A 0 -> 2 -> 5 -> null

B null

C 0 -> null

D 2 -> 5 -> null

💡 Hint

Only the non-null list contributes nodes to the merged list.

Since only the second list has nodes, the merged list is exactly that list in order.

🧠 Conceptual

expert

Time complexity of merging k sorted lists using min heap

What is the time complexity of merging k sorted lists with a total of n nodes using a min heap?

A O(n k), because each node is compared with all k lists

B O(k log n), because heap operations depend on total nodes n

C O(n log k), because each node is pushed and popped from a heap of size k

D O(n + k), because heap operations are constant time

💡 Hint

Consider how many heap operations happen and the heap size.

Each of the n nodes is pushed and popped once from a min heap of size at most k, so each heap operation costs O(log k). Total time is O(n log k).