Merge K Sorted Lists Using Min Heap in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the min heap as an empty array.

DSA Javascript

const minHeap = [1];

Drag options to blanks, or click blank then click option'

A0

B[]

Cnull

D{}

Attempts:

3 left

💡 Hint

Common Mistakes

Using an object {} instead of an array.

Initializing with null or 0.

We use an empty array [] to represent the min heap initially.

2fill in blank

medium

Complete the code to push the first node of each list into the min heap.

DSA Javascript

for (let i = 0; i < lists.length; i++) {
  if (lists[i]) {
    minHeap.push({ val: lists[i].val, listIndex: i, node: lists[i] });
  }
}

// Now build the heap
for (let i = Math.floor(minHeap.length / 2) - 1; i >= 0; i--) {
  [1](minHeap, i);
}

Drag options to blanks, or click blank then click option'

Apop

Bsort

Cpush

Dheapify

Attempts:

3 left

💡 Hint

Common Mistakes

Using sort instead of heapify.

Calling push or pop incorrectly.

We call heapify to build the min heap from the array.

3fill in blank

hard

Fix the error in the function that extracts the minimum element from the heap.

DSA Javascript

function extractMin(heap) {
  if (heap.length === 0) return null;
  const min = heap[0];
  heap[0] = heap[heap.length - 1];
  heap.pop();
  [1](heap, 0);
  return min;
}

Drag options to blanks, or click blank then click option'

Aheapify

Bpush

Cextract

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Calling pop or push instead of heapify.

Using extract which is not defined.

After removing the root, we call heapify to restore the min heap property.

4fill in blank

hard

Fill both blanks to insert the next node from the extracted list into the heap and maintain the heap property.

DSA Javascript

if (min.node.next) {
  minHeap.push({ val: min.node.next.val, listIndex: min.listIndex, node: min.node.next });
  [1](minHeap, minHeap.length - 1);
}

function [2](heap, index) {
  // heapifyDown implementation
}

Drag options to blanks, or click blank then click option'

AheapifyUp

BheapifyDown

Cheapify

DheapifyUpwards

Attempts:

3 left

💡 Hint

Common Mistakes

Using heapify instead of heapifyUp after push.

Confusing heapifyUp and heapifyDown.

We call heapifyUp after pushing a new element to fix upwards, and heapifyDown is the function that fixes downwards.

5fill in blank

hard

Fill all three blanks to complete the main loop that extracts the smallest node and appends it to the merged list.

DSA Javascript

while (minHeap.length > 0) {
  const min = [1](minHeap);
  current.next = min.node;
  current = current.next;

  if (min.node.next) {
    minHeap.push({ val: min.node.next.val, listIndex: min.listIndex, node: min.node.next });
    [2](minHeap, minHeap.length - 1);
  }

  [3](minHeap, 0);
}

Drag options to blanks, or click blank then click option'

AextractMin

BheapifyUp

CheapifyDown

DpopMin

Attempts:

3 left

💡 Hint

Common Mistakes

Using popMin which is undefined.

Mixing heapifyUp and heapifyDown order.

We extract the minimum node with extractMin, fix the heap upwards after pushing a new node with heapifyUp, and fix downwards with heapifyDown.