Kth Smallest Element Using Min Heap in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a min heap using JavaScript's built-in array and sort method.

DSA Javascript

const minHeap = arr => arr.sort((a, b) => a [1] b);

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

A-

B>

C+

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '-' causes descending order, not min heap.

Using '<' returns a boolean, leading to incorrect sorting.

To create a min heap, we sort the array in ascending order using (a, b) => a - b.

2fill in blank

medium

Complete the code to extract the smallest element from the min heap array.

DSA Javascript

const extractMin = heap => heap.[1]();

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

Apush

Bpop

Cslice

Dshift

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() removes the largest element at the end, not the smallest.

Using push() adds elements, does not remove.

The smallest element is at the start of the array in a min heap, so use shift() to remove it.

3fill in blank

hard

Fix the error in the code to find the kth smallest element using a min heap.

DSA Javascript

function kthSmallest(arr, k) {
  const heap = arr.slice().sort((a, b) => a - b);
  for (let i = 1; i < k; i++) {
    heap.[1]();
  }
  return heap[0];
}

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

Apop

Bpush

Cshift

Dslice

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() removes the largest element, not the smallest.

Using push() adds elements, does not remove.

We remove the smallest elements k-1 times using shift(), then return the next smallest at index 0.

4fill in blank

hard

Fill both blanks to create a min heap and extract the kth smallest element.

DSA Javascript

function kthSmallest(arr, k) {
  const heap = arr.slice().sort((a, b) => a [1] b);
  for (let i = 1; i < k; i++) {
    heap.[2]();
  }
  return heap[0];
}

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

A-

B>

Cshift

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' sorts descending, which is max heap behavior.

Using pop() removes last element, not smallest.

Sort ascending with - to build min heap, then remove smallest elements with shift().

5fill in blank

hard

Fill all three blanks to build a min heap, remove k-1 smallest elements, and return the kth smallest.

DSA Javascript

function kthSmallest(arr, k) {
  const heap = arr.slice().sort((a, b) => a [1] b);
  for (let i = 1; i < k; i++) {
    heap.[2]();
  }
  return heap[3];
}

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

A-

Bshift

C[0]

D[k]

Attempts:

3 left

💡 Hint

Common Mistakes

Returning heap[k] is wrong because after removing k-1 elements, kth smallest is at index 0.

Using pop() removes largest element, not smallest.

Sort ascending with -, remove smallest with shift(), then return first element [0].

Practice

1. What does the Kth Smallest Element Using Min Heap algorithm primarily do?

easy

A. Find the element that is the Kth smallest in a list using a min heap

B. Sort the entire list in ascending order

C. Find the largest element in the list

D. Remove duplicates from the list

Solution

1. Step 1: Understand the min heap role

   A min heap always keeps the smallest element at the root, making it easy to access the smallest values.

2. Step 2: Use min heap to find Kth smallest

   By extracting the root K times, we get the Kth smallest element.

3. Final Answer:

   Find the element that is the Kth smallest in a list using a min heap -> Option A

4. Quick Check:

   Kth smallest element = find using min heap [OK]

Hint: Extract min K times from min heap to get Kth smallest [OK]

Common Mistakes:

• Confusing min heap with max heap
• Thinking it sorts the entire list
• Assuming it finds the largest element

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

easy

A. heap.pop(element); heapifyDown(0);

B. heap.push(element); heapifyUp(heap.length - 1);

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

D. heap.shift(element); heapifyUp(heap.length - 1);

Solution

1. Step 1: Insert element at the end

   Inserting into a heap means adding the element at the end of the array.

2. Step 2: Restore heap property by heapify up

   After insertion, heapify up is called from the inserted index to maintain min heap order.

3. Final Answer:

   heap.push(element); heapifyUp(heap.length - 1); -> Option B

4. Quick Check:

   Insert + heapifyUp = heap.push(element); heapifyUp(heap.length - 1); [OK]

Hint: Insert at end, then heapify up to fix min heap [OK]

Common Mistakes:

• Using pop or shift to insert elements
• Calling heapifyDown after insertion
• Inserting at the front of the array

3. What is the output of the following code snippet?

const heap = [1, 3, 6, 5, 9, 8];
function extractMin(heap) {
  const min = heap[0];
  heap[0] = heap.pop();
  heapifyDown(heap, 0);
  return min;
}
function heapifyDown(heap, i) {
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  let smallest = i;
  if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
  if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
  if (smallest !== i) {
    [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
    heapifyDown(heap, smallest);
  }
}
console.log(extractMin(heap));

medium

A. 6

B. 3

C. 5

D. 1

Solution

1. Step 1: Extract min element

   The min element is at heap[0], which is 1.

2. Step 2: Replace root and heapify down

   Replace root with last element 8, then heapify down to restore min heap.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   extractMin returns root = 1 [OK]

Hint: extractMin returns root element of min heap [OK]

Common Mistakes:

• Returning last element instead of root
• Not heapifying down after extraction
• Confusing min heap root with max

4. Identify the bug in this code snippet for finding the Kth smallest element using a min heap:

function kthSmallest(arr, k) {
  const heap = [];
  for (const num of arr) {
    heap.push(num);
  }
  for (let i = Math.floor(heap.length / 2); i >= 0; i--) {
    heapifyDown(heap, i);
  }
  let result;
  for (let i = 0; i < k; i++) {
    result = heap.shift();
    heapifyDown(heap, 0);
  }
  return result;
}

medium

A. Using shift() removes first element but does not maintain heap structure

B. Heap is not built correctly from array

C. Loop for heapifyDown should start from 0 to end

D. Variable result is not initialized

Solution

1. Step 1: Check element removal method

   Using shift() removes first element but shifts all others, breaking heap structure.

2. Step 2: Correct removal method

   Should remove root by swapping with last element, popping last, then heapify down.

3. Final Answer:

   Using shift() removes first element but does not maintain heap structure -> Option A

4. Quick Check:

   shift() breaks heap property [OK]

Hint: Remove root by swap and pop, not shift() [OK]

Common Mistakes:

• Using shift() instead of swap and pop
• Incorrect heap building loop range
• Ignoring heapify after removal

5. Given an array [7, 10, 4, 3, 20, 15] and k = 3, what is the Kth smallest element using a min heap approach?

hard

A. 4

B. 10

C. 7

D. 3

Solution

1. Step 1: Build min heap from array

   Min heap root is smallest element: 3.

2. Step 2: Extract min 3 times

   Extract 1st min: 3, 2nd min: 4, 3rd min: 7.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   3rd smallest element = 7 [OK]

Hint: Extract min K times; last extracted is Kth smallest [OK]

Common Mistakes:

• Counting index instead of extraction times
• Confusing Kth smallest with Kth largest
• Not building min heap properly