Kth Smallest Element Using Min Heap in DSA Javascript - Build from Scratch

Kth Smallest Element Using Min Heap

📖 Scenario: You are working with a list of numbers representing daily temperatures. You want to find the kth smallest temperature to understand cooler days.

🎯 Goal: Build a program that uses a min heap to find the kth smallest number in a list.

📋 What You'll Learn

Create an array called temperatures with exact values

Create a variable k to select the kth smallest element

Build a min heap from the temperatures array

Extract the kth smallest element from the min heap

Print the kth smallest temperature

💡 Why This Matters

🌍 Real World

Finding the kth smallest or largest value is useful in statistics, data analysis, and real-time systems like temperature monitoring or stock prices.

💼 Career

Understanding heaps and kth element selection is important for software engineers working on algorithms, data processing, and performance optimization.

1

Create the temperatures array

Create an array called temperatures with these exact values: [23, 17, 35, 12, 28, 30, 15]

DSA Javascript

# Create the temperatures array
// Your code here

Hint

Use const temperatures = [23, 17, 35, 12, 28, 30, 15]; to create the array.

2

Set the kth position

Create a variable called k and set it to 3 to find the 3rd smallest temperature

DSA Javascript

const temperatures = [23, 17, 35, 12, 28, 30, 15];
// Set k to 3
// Your code here

Hint

Use const k = 3; to set the kth smallest element to find.

3

Build min heap and extract kth smallest

Create a min heap from temperatures using a MinHeap class, then extract the smallest element k times to find the kth smallest temperature

DSA Javascript

const temperatures = [23, 17, 35, 12, 28, 30, 15];
const k = 3;

// Implement MinHeap class and find kth smallest
// Your code here

Hint

Build a MinHeap class with insert and extractMin methods. Insert all temperatures, then extract min k times.

4

Print the kth smallest temperature

Print the variable kthSmallest to display the kth smallest temperature

DSA Javascript

const temperatures = [23, 17, 35, 12, 28, 30, 15];
const k = 3;

class MinHeap {
  constructor() {
    this.heap = [];
  }

  getParentIndex(i) { return Math.floor((i - 1) / 2); }
  getLeftChildIndex(i) { return 2 * i + 1; }
  getRightChildIndex(i) { return 2 * i + 2; }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = this.getParentIndex(index);
      if (this.heap[parentIndex] > this.heap[index]) {
        this.swap(parentIndex, index);
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  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.heapifyDown();
    return min;
  }

  heapifyDown() {
    let index = 0;
    const length = this.heap.length;
    while (this.getLeftChildIndex(index)  this.heap[smallerChildIndex]) {
        this.swap(index, smallerChildIndex);
        index = smallerChildIndex;
      } else {
        break;
      }
    }
  }
}

const minHeap = new MinHeap();
for (const temp of temperatures) {
  minHeap.insert(temp);
}

let kthSmallest = null;
for (let i = 0; i < k; i++) {
  kthSmallest = minHeap.extractMin();
}

// Print the kth smallest temperature
console.log(kthSmallest);

Hint

Use console.log(kthSmallest); to print the result.

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