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

Concept Flow - Kth Largest Element Using Max Heap

Build Max Heap from array

↓

Extract max element (root)

↓

Replace root with last element

↓

Heapify to restore max heap

↓

Repeat extraction k times

↓

Last extracted element is kth largest

Build a max heap from the array, then remove the largest element k times. The last removed element is the kth largest.

Execution Sample

DSA Typescript

function heapify(nums: number[], heapSize: number, i: number): void {
  let largest = i;
  const l = 2 * i + 1;
  const r = 2 * i + 2;
  if (l < heapSize && nums[l] > nums[largest]) largest = l;
  if (r < heapSize && nums[r] > nums[largest]) largest = r;
  if (largest !== i) {
    [nums[i], nums[largest]] = [nums[largest], nums[i]];
    heapify(nums, heapSize, largest);
  }
}

function findKthLargest(nums: number[], k: number): number {
  let heapSize = nums.length;
  for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
    heapify(nums, heapSize, i);
  }
  for (let i = 0; i < k; i++) {
    const max = nums[0];
    nums[0] = nums[heapSize - 1];
    heapSize--;
    heapify(nums, heapSize, 0);
    if (i === k - 1) return max;
  }
  return -1;
}

This code builds a max heap from the array (O(n)) and extracts the max element k times (O(k log n)) to find the kth largest.

Execution Table

Step	Operation	Nodes in Heap Array	Pointer Changes	Visual State (Heap Tree)
1	Build max heap from [3,2,1,5,6,4]	[6,5,4,3,2,1]	Heap built, root at index 0	6 / \ 5 4 / \ / 3 2 1
2	Extract max (6)	[5,3,4,1,2]	Root replaced by last element (1), heapify from root	5 / \ 3 4 / \ 1 2
3	Extract max (5)	[4,3,2,1]	Root replaced by last element (2), heapify from root	4 / \ 3 2 / 1
4	Extract max (4)	[3,1,2]	Root replaced by last element (1), heapify from root	3 / \ 1 2
5	Extract max (3)	[2,1]	Root replaced by last element (1), heapify from root	2 / 1
6	Extract max (2)	[1]	Root replaced by last element (1), heapify not needed	1
7	Extract max (1)	[]	Heap empty after extraction	(empty)

💡 Extraction stops after k times; last extracted element is kth largest.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
nums (heap array)	[3,2,1,5,6,4]	[5,3,4,1,2]	[4,3,2,1]	[3,1,2]	[2,1]	[1]	[]	[]
extracted max	N/A	6	5	4	3	2	1	N/A
k	3 (example)	3	3	3	3	3	3	3

Key Moments - 3 Insights

Why do we replace the root with the last element before heapifying?

Because the root (max element) is removed, we need to fill the root position to keep the heap complete. The last element moves to root, then heapify fixes the heap property (see execution_table step 2).

Why do we heapify only from the root after extraction?

Only the root may violate the max heap property after replacement. Heapify from root restores order efficiently (see execution_table steps 2-6).

How do we know when to stop extracting elements?

We extract exactly k times. The last extracted max is the kth largest element (see exit_note and variable_tracker extracted max after 3 extractions).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the root of the heap after extraction?

A 5

B 1

C 4

D 3

💡 Hint

Check the 'Visual State' column at step 3 in execution_table.

After the first extraction and heapify (step 2), what is the heap array?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Look at the 'Nodes in Heap Array' column in execution_table.

If k=4, what is the extracted max value after the last extraction?

A 4

B 3

C 5

D 6

💡 Hint

Check the 'extracted max' row in variable_tracker after 4 extractions.

Concept Snapshot

Kth Largest Element Using Max Heap:
- Build max heap from array
- Extract max element k times
- Each extraction: replace root with last element, then heapify
- Last extracted max is kth largest
- Efficient for large arrays, O(n + k log n) time

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 times. Each extraction removes the root, replaces it with the last element in the heap, and heapifies from the root to restore the max heap property. After k extractions, the last extracted element is the kth largest. This method efficiently finds the kth largest without sorting the entire array.