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.