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.

Practice

1. What is the main idea behind finding the kth largest element using a max heap?

easy

A. Build a max heap from the array and extract the max element k times

B. Sort the array and pick the kth element from the start

C. Use a min heap to store all elements and pop k times

D. Reverse the array and pick the kth element

Solution

1. Step 1: Understand max heap property

   A max heap always keeps the largest element at the root, so extracting the root gives the largest element.

2. Step 2: Extract max k times to get the kth largest

   By removing the root k times, the last extracted element is the kth largest.

3. Final Answer:

   Build max heap and extract max k times -> Option A

4. Quick Check:

   Max heap extraction = kth largest element [OK]

Hint: Extract max from max heap k times to find kth largest [OK]

Common Mistakes:

• Using min heap instead of max heap
• Sorting and picking wrong index
• Extracting fewer or more than k times

2. Which of the following is the correct way to create a max heap from an array arr in JavaScript using a custom heap class?

easy

A. const maxHeap = new MaxHeap(arr); maxHeap.heapify();

B. const maxHeap = new MaxHeap(); maxHeap.insert(arr);

C. const maxHeap = new MaxHeap(); maxHeap.build(arr);

D. const maxHeap = new MaxHeap(arr); maxHeap.buildHeap();

Solution

1. Step 1: Recognize typical max heap initialization

   Usually, a max heap class accepts an array and has a method like buildHeap() to create the heap structure.

2. Step 2: Identify correct method call

   buildHeap() is the standard method to convert the array into a max heap, so calling it after initialization is correct.

3. Final Answer:

   const maxHeap = new MaxHeap(arr); maxHeap.buildHeap(); -> Option D

4. Quick Check:

   buildHeap() builds max heap from array [OK]

Hint: Use buildHeap() after passing array to MaxHeap constructor [OK]

Common Mistakes:

• Calling insert with whole array instead of single elements
• Using wrong method names like heapify or build
• Not calling any method to build the heap

3. What will be the output of the following code snippet?

class MaxHeap {
  constructor(arr) {
    this.heap = arr;
    this.buildHeap();
  }
  buildHeap() {
    for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
      this.heapify(i);
    }
  }
  heapify(i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < this.heap.length && this.heap[left] > this.heap[largest]) largest = left;
    if (right < this.heap.length && 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];
    this.heap[0] = this.heap.pop();
    this.heapify(0);
    return max;
  }
}

const arr = [3, 2, 1, 5, 6, 4];
const maxHeap = new MaxHeap(arr);
let kthLargest;
for (let i = 0; i < 2; i++) {
  kthLargest = maxHeap.extractMax();
}
console.log(kthLargest);

medium

A. 6

B. 5

C. 4

D. 3

Solution

1. Step 1: Build max heap from array

   Array [3,2,1,5,6,4] becomes max heap with root 6 after buildHeap.

2. Step 2: Extract max twice

   First extractMax returns 6, second extractMax returns 5, so kthLargest after loop is 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   2nd largest element = 5 [OK]

Hint: Extract max twice from max heap to get 2nd largest [OK]

Common Mistakes:

• Assuming heap root changes incorrectly after extraction
• Confusing 1st largest with 2nd largest
• Not updating heap after extraction

4. Identify the bug in the following code that tries to find the 3rd largest element using a max heap:

class MaxHeap {
  constructor(arr) {
    this.heap = arr;
    this.buildHeap();
  }
  buildHeap() {
    for (let i = 0; i < this.heap.length / 2; i++) {
      this.heapify(i);
    }
  }
  heapify(i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < this.heap.length && this.heap[left] > this.heap[largest]) largest = left;
    if (right < this.heap.length && 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];
    this.heap[0] = this.heap.pop();
    this.heapify(0);
    return max;
  }
}

const arr = [7, 10, 4, 3, 20, 15];
const maxHeap = new MaxHeap(arr);
let kthLargest;
for (let i = 0; i < 3; i++) {
  kthLargest = maxHeap.extractMax();
}
console.log(kthLargest);

medium

A. The buildHeap loop should run backwards from middle to 0

B. extractMax should not call heapify after popping

C. heapify should swap with smallest child instead of largest

D. The array should be sorted before building the heap

Solution

1. Step 1: Analyze buildHeap loop direction

   Heap building requires heapify calls from last parent to root, so loop must run backwards from middle to 0.

2. Step 2: Identify incorrect loop direction

   Current loop runs forwards, which does not correctly heapify the tree, causing incorrect heap structure.

3. Final Answer:

   The buildHeap loop should run backwards from middle to 0 -> Option A

4. Quick Check:

   buildHeap loop direction = backwards [OK]

Hint: buildHeap loop must run backwards from middle to root [OK]

Common Mistakes:

• Running buildHeap loop forwards
• Not calling heapify after extractMax
• Swapping with wrong child in heapify

5. Given an array arr = [12, 3, 5, 7, 19, 0, 4], write a JavaScript function using a max heap to find the 4th largest element. What is the output of your function?

hard

A. 4

B. 5

C. 7

D. 3

Solution

1. Step 1: Build max heap from array

   Array becomes max heap with root 19 after heapify.

2. Step 2: Extract max 4 times

   Extracted elements in order: 19, 12, 7, 5. The 4th largest is 7.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   4th largest element = 7 [OK]

Hint: Extract max k times; last extracted is kth largest [OK]

Common Mistakes:

• Extracting fewer times than k
• Confusing 3rd largest with 4th largest
• Not rebuilding heap after extraction