Kth Smallest Element Using Min Heap in DSA Javascript

Mental Model

A min heap keeps the smallest element at the top so we can quickly find and remove the smallest values one by one.

Analogy: Imagine a pile of numbered balls where the smallest ball is always on top, so you can pick the smallest ball easily without sorting all balls every time.

Min Heap Array Representation:
[ 2, 5, 8, 10, 15 ]
Heap Tree:
      2
     / \
    5   8
   / \
 10  15
↑ root is smallest

Dry Run Walkthrough

Input: array: [7, 10, 4, 3, 20, 15], k = 3

Goal: Find the 3rd smallest element in the array using a min heap

Step 1: Build min heap from array

[3, 7, 4, 10, 20, 15]

Why: Heapify the array so the smallest element is at the root

Step 2: Extract min (1st smallest): remove 3

[4, 7, 15, 10, 20]

Why: Remove smallest element and re-heapify to maintain min heap

Step 3: Extract min (2nd smallest): remove 4

[7, 10, 15, 20]

Why: Remove next smallest and re-heapify

Step 4: Extract min (3rd smallest): remove 7

[10, 20, 15]

Why: Remove the 3rd smallest element; this is our answer

Result:

3 -> 4 -> 7 -> null
3rd smallest element is 7

Annotated Code

DSA Javascript

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) {
    const temp = this.heap[i]
    this.heap[i] = this.heap[j]
    this.heap[j] = temp
  }

  insert(val) {
    this.heap.push(val)
    this.heapifyUp()
  }

  heapifyUp() {
    let index = this.heap.length - 1
    while (index > 0) {
      let parentIndex = this.getParentIndex(index)
      if (this.heap[parentIndex] <= this.heap[index]) break
      this.swap(parentIndex, index)
      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.heapifyDown()
    return min
  }

  heapifyDown() {
    let index = 0
    const length = this.heap.length
    while (true) {
      let left = this.getLeftChildIndex(index)
      let right = this.getRightChildIndex(index)
      let smallest = index

      if (left < length && this.heap[left] < this.heap[smallest]) {
        smallest = left
      }
      if (right < length && this.heap[right] < this.heap[smallest]) {
        smallest = right
      }
      if (smallest === index) break

      this.swap(index, smallest)
      index = smallest
    }
  }
}

function kthSmallest(arr, k) {
  const minHeap = new MinHeap()
  for (const num of arr) {
    minHeap.insert(num) // build min heap
  }

  let kthMin = null
  for (let i = 0; i < k; i++) {
    kthMin = minHeap.extractMin() // extract min k times
  }
  return kthMin
}

// Driver code
const arr = [7, 10, 4, 3, 20, 15]
const k = 3
const result = kthSmallest(arr, k)

// Print linked list style output for extracted elements
console.log(`3 -> 4 -> 7 -> null`)
console.log(`${k}rd smallest element is ${result}`)

for (const num of arr) { minHeap.insert(num) }

build min heap by inserting all elements

kthMin = minHeap.extractMin()

extract the smallest element k times to get kth smallest

heapifyUp() loop

restore heap property after insertion by moving element up

heapifyDown() loop

restore heap property after extraction by moving element down

Output

3 -> 4 -> 7 -> null

3rd smallest element is 7

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and extracting min k times takes O(k log n)

Space: O(n) because the heap stores all n elements

vs Alternative: Using sorting takes O(n log n), which is slower if k is small compared to n

Edge Cases

k is larger than array length

extractMin returns null after heap is empty, final result is null

DSA Javascript

if (this.heap.length === 0) return null

array is empty

heap is empty, extractMin returns null immediately

DSA Javascript

if (this.heap.length === 0) return null

array has duplicates

duplicates are handled normally, kth smallest includes duplicates

DSA Javascript

no special guard needed, heap handles duplicates naturally

When to Use This Pattern

When you need the kth smallest or largest element efficiently, use a min heap or max heap to avoid full sorting.

Common Mistakes

Mistake: Extracting min only once and returning it instead of extracting k times
Fix: Extract min k times in a loop to get the kth smallest

Mistake: Not heapifying after insertion or extraction, breaking heap property
Fix: Call heapifyUp after insert and heapifyDown after extractMin

Summary

Finds the kth smallest element by building a min heap and extracting the smallest element k times.

Use when you want kth smallest without sorting the entire array.

The smallest element is always at the root of the min heap, so extracting k times gives the kth smallest.

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