Kth Largest Element Using Max Heap in DSA Javascript - Execution Trace

Concept Flow - Kth Largest Element Using Max Heap

Build Max Heap from array

↓

Extract max element k-1 times

↓

Heap root is kth largest

↓

Return root value

Build a max heap from the array, remove the largest element k-1 times, then the root is the kth largest.

Execution Sample

DSA Javascript

function findKthLargest(nums, k) {
  buildMaxHeap(nums);
  for (let i = 0; i < k - 1; i++) {
    extractMax(nums);
  }
  return nums[0];
}

Find kth largest by building max heap and extracting max k-1 times.

Execution Table

Step	Operation	Heap Array State	Pointer Changes	Visual State
1	Build max heap from [3,2,1,5,6,4]	[6,5,4,3,2,1]	heapify done	Heap as tree: 6 / \ 5 4 / \ / 3 2 1
2	Extract max (remove 6)	[5,3,4,1,2]	Swap root with last, remove last, heapify root	Heap as tree: 5 / \ 3 4 / \ 1 2
3	Extract max (remove 5)	[4,3,2,1]	Swap root with last, remove last, heapify root	Heap as tree: 4 / \ 3 2 / 1
4	k-1 extractions complete	[4,3,2,1]	No change	Heap as tree: 4 / \ 3 2 / 1
5	Return root as 3rd largest	[4,3,2,1]	No change	Heap root 4 is the 3rd largest element

💡 After extracting max k-1=2 times, root is kth largest

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
nums	[3,2,1,5,6,4]	[6,5,4,3,2,1]	[5,3,4,1,2]	[4,3,2,1]	[4,3,2,1]	[4,3,2,1]
k	3	3	3	3	3	3
heap size	6	6	5	4	4	4

Key Moments - 3 Insights

Why do we remove the root and then heapify?

Because the root is the largest element, removing it and heapifying restores max heap property as shown in steps 2-4 of execution_table.

Why is the kth largest element at the root after k-1 extractions?

Each extraction removes the largest element, so after k-1 removals, the root is the kth largest, as shown in step 5.

Why do we swap root with last element before removing?

Swapping allows removing the last element easily and then heapifying from root to maintain heap structure, as seen in steps 2-4.

Visual Quiz - 3 Questions

Look at the execution_table at Step 2, what is the heap array after extracting max once?

A [4,3,2,1]

B [5,3,4,1,2]

C [6,5,4,3,2,1]

D [3,1,2]

💡 Hint

Check the 'Heap Array State' column at Step 2 in execution_table.

At which step does the heap size reduce to 4?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at variable_tracker row for 'heap size' after each step.

If k was 2 instead of 3, what would be the root after extraction?

A 5

B 4

C 3

D 6

💡 Hint

After k-1=1 extraction, check heap root in execution_table Step 2.

Concept Snapshot

Kth Largest Element Using Max Heap:
- Build max heap from array
- Extract max element k-1 times
- Root of heap is kth largest
- Extraction: swap root with last, remove last, heapify root
- Time: O(n + k log n) approx

Full Transcript

To find the kth largest element using a max heap, first build a max heap from the input array. The max heap ensures the largest element is at the root. Then, extract the max element k-1 times by swapping the root with the last element, removing the last element, and heapifying the root to restore heap order. After these extractions, the root of the heap is the kth largest element. This process is shown step-by-step in the execution table, tracking the heap array and its tree structure. Variables like heap size and array state change after each extraction. Key moments clarify why we swap and heapify, and why the kth largest is at the root after k-1 removals. The visual quiz tests understanding of heap state after extractions and the effect of changing k.

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