Kth Largest Element Using Max Heap in DSA Javascript

Mental Model

A max heap keeps the largest element at the top, so repeatedly removing the top gives the next largest elements.

Analogy: Imagine a pile of boxes stacked so the biggest box is always on top. Taking off the top box reveals the next biggest box underneath.

Max Heap Array Representation:
[ 9, 7, 8, 5, 6, 3, 4 ]
Heap Tree:
       9
     /   \
    7     8
   / \   / \
  5   6 3   4
↑ (root is largest)

Dry Run Walkthrough

Input: array: [3, 1, 9, 7, 5, 8, 6], k = 3

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

Step 1: Build max heap from array

[9, 7, 8, 1, 5, 3, 6]

Why: We rearrange to satisfy max heap property so largest element is at root

Step 2: Remove max (9), replace root with last element (6), heapify

[8, 7, 6, 1, 5, 3]

Why: Removing largest element to find next largest, then restore heap

Step 3: Remove max (8), replace root with last element (3), heapify

[7, 5, 6, 1, 3]

Why: Remove second largest, restore heap for next largest

Step 4: Remove max (7), replace root with last element (3), heapify

[6, 5, 3, 1]

Why: Remove third largest, which is the kth largest element

Result:

Final heap after 3 removals: [6, 5, 3, 1]
3rd largest element is 7

Annotated Code

DSA Javascript

class MaxHeap {
  constructor(arr) {
    this.heap = arr;
    this.buildHeap();
  }

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

  heapify(i) {
    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() {
    if (this.heap.length === 0) return null;
    const max = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.heapify(0);
    }
    return max;
  }
}

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

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

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

build max heap 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 to maintain max heap and heapify subtree

const max = this.heap[0]; const end = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = end; this.heapify(0); } return max;

extract max element and restore heap

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

extract max k times to get kth largest

Output

3rd largest element is 7

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and each extractMax 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 heap approach when k is small

Edge Cases

k is larger than array length

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

DSA Javascript

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

array is empty

buildHeap does nothing, extractMax returns null immediately

DSA Javascript

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

array has duplicates

duplicates are handled normally, kth largest is correct

DSA Javascript

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 remove the largest elements.

Common Mistakes

Mistake: Not rebuilding the heap after extracting max
Fix: Call heapify on root after replacing root with last element to restore heap

Mistake: Building min heap instead of max heap
Fix: Ensure heapify compares children to find the largest, not smallest

Summary

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

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

The largest element is always at the root, so removing it k times reveals the kth largest.