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.