Kth Smallest Element Using Min Heap in DSA Typescript

Mental Model

A min heap always keeps the smallest element at the top, so we can remove the smallest elements one by one until we reach the kth smallest.

Analogy: Imagine a line of kids waiting to get ice cream, where the shortest kid is always at the front. To find the kth shortest kid, you let the first kid get ice cream and leave, then the next shortest moves to the front, and so on until you reach the kth kid.

Min Heap Array: [2, 3, 5, 7, 8, 10]
Heap structure:
      2
     / \
    3   5
   / \  /
  7  8 10
↑ (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

Min Heap Array: [3, 7, 4, 10, 20, 15]
Heap structure:
      3
     / \
    7   4
   / \  /
  10 20 15

Why: We need the smallest element at the top to remove it easily

Step 2: Remove smallest element (3) from heap

Min Heap Array after removal: [4, 7, 15, 10, 20]
Heap structure:
      4
     / \
    7   15
   / \
  10 20

Why: Removing the smallest element moves us closer to the kth smallest

Step 3: Remove next smallest element (4) from heap

Min Heap Array after removal: [7, 10, 15, 20]
Heap structure:
      7
     / \
    10  15
   /
  20

Why: We continue removing smallest elements to reach the kth

Step 4: Remove next smallest element (7) from heap

Min Heap Array after removal: [10, 20, 15]
Heap structure:
      10
     / \
    20  15

Why: The 3rd removed element is the 3rd smallest in the array

Result:

Min Heap Array after 3 removals: [10, 20, 15]
The 3rd smallest element is 7

Annotated Code

DSA Typescript

class MinHeap {
  heap: number[] = [];

  constructor(arr: number[]) {
    this.heap = arr.slice();
    this.buildHeap();
  }

  private buildHeap() {
    for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
      this.heapifyDown(i);
    }
  }

  private heapifyDown(i: number) {
    let smallest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

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

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

    if (smallest !== i) {
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      this.heapifyDown(smallest);
    }
  }

  extractMin(): number | null {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0 && end !== undefined) {
      this.heap[0] = end;
      this.heapifyDown(0);
    }
    return min;
  }
}

function kthSmallest(arr: number[], k: number): number | null {
  const minHeap = new MinHeap(arr);
  let result: number | null = null;
  for (let i = 0; i < k; i++) {
    result = minHeap.extractMin();
    if (result === null) return null;
  }
  return result;
}

// Driver code
const arr = [7, 10, 4, 3, 20, 15];
const k = 3;
const kth = kthSmallest(arr, k);
console.log(`${k}th smallest element is ${kth}`);

for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) { this.heapifyDown(i); }

Build min heap by heapifying from bottom non-leaf nodes up

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

Handle empty heap edge case before extraction

const min = this.heap[0];

Store smallest element at root to return

const end = this.heap.pop();

Remove last element to replace root

if (this.heap.length > 0 && end !== undefined) { this.heap[0] = end; this.heapifyDown(0); }

Replace root with last element and restore heap property

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

Extract min k times to get kth smallest element

Output

3th smallest element is 7

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and each of the k extractions takes O(log n)

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

vs Alternative: Compared to sorting the array which takes O(n log n), this method can be faster when k is small

Edge Cases

k is larger than array length

Function returns null because kth smallest does not exist

DSA Typescript

if (result === null) return null;

empty array

Function returns null immediately

DSA Typescript

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

array with duplicate elements

Duplicates are treated normally; kth smallest counts duplicates as separate elements

DSA Typescript

No special guard needed; heap handles duplicates naturally

When to Use This Pattern

When you need the kth smallest or largest element efficiently, and the data is unsorted, reach for the min heap pattern because it lets you remove smallest elements quickly without full sorting.

Common Mistakes

Mistake: Extracting min fewer than k times and returning wrong element
Fix: Ensure to extract min exactly k times to get the kth smallest

Mistake: Not rebuilding heap after extraction
Fix: After removing root, replace it with last element and heapify down to restore heap property

Summary

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

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

The smallest element is always at the root of the min heap, so repeated extraction leads to the kth smallest.