Kth Smallest Element Using Min Heap in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kth Smallest Element Extraction

What is the output of the following JavaScript code that finds the 3rd smallest element using a min heap?

DSA Javascript

class MinHeap {
  constructor() {
    this.heap = [];
  }
  insert(val) {
    this.heap.push(val);
    this.bubbleUp();
  }
  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }
  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);
    return min;
  }
  sinkDown(index) {
    const length = this.heap.length;
    const element = this.heap[index];
    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let swap = null;
      if (leftChildIdx < length) {
        if (this.heap[leftChildIdx] < element) swap = leftChildIdx;
      }
      if (rightChildIdx < length) {
        if ((swap === null && this.heap[rightChildIdx] < element) || (swap !== null && this.heap[rightChildIdx] < this.heap[leftChildIdx])) {
          swap = rightChildIdx;
        }
      }
      if (swap === null) break;
      [this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]];
      index = swap;
    }
  }
}

function kthSmallest(arr, k) {
  const minHeap = new MinHeap();
  for (const num of arr) {
    minHeap.insert(num);
  }
  let result = null;
  for (let i = 0; i < k; i++) {
    result = minHeap.extractMin();
  }
  return result;
}

const arr = [7, 10, 4, 3, 20, 15];
const k = 3;
console.log(kthSmallest(arr, k));

A 7

B 4

C 10

D 3

💡 Hint

Remember the min heap always extracts the smallest element first.

The sorted array is [3, 4, 7, 10, 15, 20]. The 3rd smallest element is 7.

🧠 Conceptual

intermediate

Understanding Min Heap Property

Which of the following statements correctly describes the min heap property?

A Every parent node is smaller than or equal to its children nodes.

B Every parent node is larger than or equal to its children nodes.

C All leaf nodes are smaller than the root node.

D The heap is always a sorted array.

💡 Hint

Think about how the smallest element is always at the top.

In a min heap, each parent node is smaller than or equal to its children, ensuring the smallest element is at the root.

❓ Predict Output

advanced

Output After Multiple ExtractMin Calls

Given the following min heap operations, what is the output after extracting the min element 4 times?

DSA Javascript

const heap = new MinHeap();
[12, 3, 17, 8, 10, 5].forEach(n => heap.insert(n));
const results = [];
for (let i = 0; i < 4; i++) {
  results.push(heap.extractMin());
}
console.log(results);

A [3, 5, 10, 12]

B [3, 5, 8, 10]

C [3, 8, 10, 12]

D [3, 5, 8, 12]

💡 Hint

Extracting min removes the smallest element each time.

The inserted elements sorted are [3, 5, 8, 10, 12, 17]. Extracting min 4 times returns the first four smallest: 3, 5, 8, 10.

🔧 Debug

advanced

Identify the Bug in Min Heap Insert Method

What error will occur when running this insert method in the MinHeap class?

DSA Javascript

insert(val) {
  this.heap.push(val);
  let index = this.heap.length - 1;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    if (this.heap[parentIndex] <= this.heap[index]) break;
    [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
    index = parentIndex;
  }
}

A No error; code runs correctly.

B SyntaxError due to missing semicolon.

C TypeError because this.heap is undefined.

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

💡 Hint

Check how parent index is calculated in a binary heap.

Parent index should be Math.floor((index - 1) / 2). Using Math.floor(index / 2) causes incorrect parent calculation and breaks heap property.

🚀 Application

expert

Kth Smallest Element with Large Data

You have an array of 1 million random integers. Which approach is most efficient to find the 500th smallest element?

A Sort the entire array and pick the 500th element.

B Build a min heap of all elements and extract min 500 times.

C Use a max heap of size 500 to track the 500 smallest elements while iterating once.

D Use a linear search to find the 500th smallest element.

💡 Hint

Consider time and space efficiency for large data.

Using a max heap of size 500 keeps track of the smallest 500 elements efficiently in O(n log k) time, better than sorting or building a full min heap.

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