Kth Largest Element Using Max Heap in DSA Typescript

Mental Model

A max heap keeps the largest element at the top, so removing the top element k times gives the kth largest.

Analogy: Imagine a pile of books stacked so the biggest book is always on top. Taking the top book off repeatedly lets you find the kth biggest book.

       [10]
      /     \
   [7]       [9]
  /   \     /   \
[3]  [5]  [8]  [4]

Dry Run Walkthrough

Input: array: [3, 10, 5, 7, 9, 8, 4], k = 3

Goal: Find the 3rd largest element in the array using a max heap

Step 1: Build max heap from array

       [10]
      /     \
   [9]       [8]
  /   \     /   \
[3]  [7]  [5]  [4]

Why: We need the largest element at the root to extract it easily

Step 2: Extract max (10), remove root and reheapify

       [9]
      /     \
   [7]       [8]
  /   \     /   
[3]  [4]  [5]  null

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

Step 3: Extract max (9), remove root and reheapify

       [8]
      /     \
   [7]       [5]
  /   \     /   
[3]  [4]  null  null

Why: Second largest removed, next largest is now root

Step 4: Extract max (8), this is the 3rd largest element

       [7]
      /     \
   [4]       [5]
  /   \     /   
[3]  null  null  null

Why: The root now is the kth largest element extracted

Result:

3rd largest element is 8

Annotated Code

DSA Typescript

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

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

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

  heapify(i: number) {
    const n = this.heap.length;
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < n && this.heap[left] > this.heap[largest]) {
      largest = left;
    }

    if (right < n && this.heap[right] > this.heap[largest]) {
      largest = right;
    }

    if (largest !== i) {
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      this.heapify(largest);
    }
  }

  extractMax(): number | null {
    if (this.heap.length === 0) return null;
    const max = this.heap[0];
    this.heap[0] = this.heap[this.heap.length - 1];
    this.heap.pop();
    this.heapify(0);
    return max;
  }
}

function findKthLargest(arr: number[], k: number): number | null {
  const maxHeap = new MaxHeap(arr);
  let kthLargest: number | null = null;
  for (let i = 0; i < k; i++) {
    kthLargest = maxHeap.extractMax();
  }
  return kthLargest;
}

// Driver code
const arr = [3, 10, 5, 7, 9, 8, 4];
const k = 3;
const result = findKthLargest(arr, k);
console.log(`${k}th largest element is ${result}`);

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

build max heap by heapifying from bottom non-leaf nodes up

if (left < n && this.heap[left] > this.heap[largest]) { largest = left; }

find largest among node and left child

if (right < n && this.heap[right] > this.heap[largest]) { largest = right; }

find largest among current largest and right child

if (largest !== i) { swap and heapify(largest); }

swap and continue heapify to maintain max heap property

const max = this.heap[0]; this.heap[0] = this.heap.pop(); this.heapify(0); return max;

extract max root, replace with last element, then heapify root

for (let i = 0; i < k; i++) { kthLargest = maxHeap.extractMax(); }

extract max k times to get kth largest

Output

3th largest element is 8

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and each extract max takes O(log n) repeated k times

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

vs Alternative: Sorting the array takes O(n log n), which is slower than building a heap plus k extractions when k is small

Edge Cases

k is larger than array length

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

DSA Typescript

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

array is empty

heap is empty, extractMax returns null immediately

DSA Typescript

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

array has duplicates

duplicates are handled normally, kth largest is correct

DSA Typescript

no special guard needed, heap property handles duplicates

When to Use This Pattern

When asked to find the kth largest element efficiently, think of using a max heap to repeatedly extract the largest elements.

Common Mistakes

Mistake: Not rebuilding the heap after extracting max, causing incorrect heap structure
Fix: Call heapify(0) after replacing root with last element to maintain max heap

Mistake: Extracting max fewer or more than k times
Fix: Use a loop to extract max exactly k times

Summary

Finds the kth largest element by building a max heap and extracting the max k times.

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

The largest element is always at the root of the max heap, so repeated extraction gives kth largest.