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.