Kth Largest Element Using Max Heap in DSA Java - 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 extract the maximum element k times. The last extracted element is the kth largest.

Execution Sample

DSA Java

int kthLargest(int[] arr, int k) {
  buildMaxHeap(arr);
  int result = -1;
  for (int i = 0; i < k; i++) {
    result = extractMax(arr);
  }
  return result;
}

Builds a max heap and extracts the max element k times to find the kth largest.

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]	heap built	6 / \ 5 4 / \ / 3 2 1
2	Extract max (1st time)	[1, 5, 4, 3, 2]	root replaced with last element 1	1 / \ 5 4 / \ 3 2
3	Heapify after extraction	[5, 3, 4, 1, 2]	swap 1 with 5	5 / \ 3 4 / 1 2
4	Extract max (2nd time)	[2, 3, 4, 1]	root replaced with last element 2	2 / \ 3 4 / 1
5	Heapify after extraction	[4, 3, 2, 1]	swap 2 with 4	4 / \ 3 2 / 1
6	Extract max (3rd time)	[1, 3, 2]	root replaced with last element 1	1 / \ 3 2
7	Heapify after extraction	[3, 1, 2]	swap 1 with 3	3 / \ 1 2
8	Extract max (4th time)	[2, 1]	root replaced with last element 2	2 / 1
9	Heapify after extraction	[2, 1]	no swap needed	2 / 1
10	Extract max (5th time)	[1]	root replaced with last element 1	1
11	Heapify after extraction	[1]	no swap needed	1
12	Return kth largest element	4	last extracted max	4

💡 After 3 extractions (k=3), the last extracted max is the 3rd largest element.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
Heap Array	[3, 2, 1, 5, 6, 4]	[5, 3, 4, 1, 2]	[4, 3, 2, 1]	[3, 1, 2]	[2, 1]	[1]	[1]
Extracted Max	N/A	6	5	4	3	2	1
k	3	3	3	3	3	3	3
Result	N/A	6	5	4	3	2	1

Key Moments - 3 Insights

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

Replacing the root with the last element keeps the heap complete (no gaps). Then heapify restores the max heap property. See execution_table rows 2 and 3.

Why does heapify swap the root down the tree?

Heapify swaps the root with the larger child to maintain the max heap property where parents are always larger than children. See execution_table rows 3, 5, and 7.

How do we know when to stop extracting max elements?

We stop after extracting max k times. The last extracted max is the kth largest element. See execution_table row 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the heap array state after heapify?

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

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

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

D [4, 3, 2, 1]

💡 Hint

Check the 'Heapify after extraction' operation in execution_table row 3.

At which step does the heap array first become [4, 3, 2, 1]?

A Step 4

B Step 5

C Step 6

D Step 3

💡 Hint

Look at the heap array state after heapify in execution_table row 5.

If k was 2 instead of 3, what would be the last extracted max element?

A 5

B 6

C 4

D 3

💡 Hint

Check the 'Extract max' operations and extracted max values in variable_tracker.

Concept Snapshot

Kth Largest Element Using Max Heap:
- Build max heap from array
- Extract max element k times
- Each extraction removes root and heapifies
- Last extracted max is kth largest
- Time complexity: O(n + k log n)

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, and heapifies to restore the max heap property. After k extractions, the last extracted element is the kth largest. This process is efficient because heap operations take logarithmic time. The execution table shows the heap array and tree structure changing step by step, with pointer changes and heapify swaps. The variable tracker records the heap array and extracted max values after each step. Key moments clarify why we replace the root with the last element and how heapify maintains the heap. The visual quiz tests understanding of heap states and extraction steps.

Practice

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

easy

A. Build a min heap and extract the min element k times

B. Sort the array and pick the element at index k

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

D. Use a hash map to count frequencies and find the kth largest

Solution

1. Step 1: Build a max heap from the array

   A max heap always keeps the largest element at the root, so building it organizes the data for easy extraction.

2. Step 2: Extract the max element k times

   Each extraction removes the largest element. After k extractions, the last extracted element is the kth largest.

3. Final Answer:

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

4. Quick Check:

   Max heap extraction = kth largest element [OK]

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

Common Mistakes:

• Using min heap instead of max heap
• Sorting and picking wrong index
• Confusing kth largest with kth smallest

2. Which of the following Java code snippets correctly creates a max heap using PriorityQueue?

easy

A. PriorityQueue<Integer> maxHeap = new PriorityQueue<>();

B. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

C. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.naturalOrder());

D. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.nullsFirst());

Solution

1. Step 1: Understand Java PriorityQueue default behavior

   By default, PriorityQueue is a min heap, so PriorityQueue<Integer> maxHeap = new PriorityQueue<>(); creates a min heap.

2. Step 2: Use reverse order comparator for max heap

   PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); uses Collections.reverseOrder() which reverses natural order, creating a max heap.

3. Final Answer:

   PriorityQueue with reverseOrder comparator -> Option B

4. Quick Check:

   Reverse order comparator = max heap [OK]

Hint: Use Collections.reverseOrder() for max heap in Java [OK]

Common Mistakes:

• Assuming default PriorityQueue is max heap
• Using naturalOrder() which is min heap
• Using nullsFirst() which is unrelated

3. What is the output of the following Java code snippet?

int[] arr = {4, 10, 3, 5, 1};
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int num : arr) maxHeap.add(num);

int k = 3;
int kthLargest = 0;
for (int i = 0; i < k; i++) {
    kthLargest = maxHeap.poll();
}
System.out.println(kthLargest);

medium

A. 4

B. 5

C. 10

D. 3

Solution

1. Step 1: Build max heap from array

   The max heap will organize elements as [10, 5, 4, 3, 1] with 10 at root.

2. Step 2: Extract max element 3 times

   First poll: 10, second poll: 5, third poll: 4. The third extracted element is 4.

3. Step 3: Check the printed value

   The code prints the last extracted element, which is 4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   3rd largest element = 4 [OK]

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

Common Mistakes:

• Confusing kth largest with kth smallest
• Off-by-one error in loop
• Printing before extraction

4. Identify the error in the following code that tries to find the 2nd largest element using a max heap:

int[] arr = {7, 2, 9, 4};
PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
for (int num : arr) maxHeap.add(num);

int k = 2;
int kthLargest = 0;
for (int i = 0; i < k; i++) {
    kthLargest = maxHeap.poll();
}
System.out.println(kthLargest);

medium

A. kthLargest should be initialized to Integer.MIN_VALUE

B. The loop should run k+1 times

C. The array should be sorted before adding to heap

D. PriorityQueue should use Collections.reverseOrder() to create max heap

Solution

1. Step 1: Check PriorityQueue initialization

   The code uses default PriorityQueue which is a min heap, not max heap.

2. Step 2: Correct max heap creation

   To find kth largest using max heap, PriorityQueue must be created with Collections.reverseOrder().

3. Final Answer:

   PriorityQueue should use Collections.reverseOrder() to create max heap -> Option D

4. Quick Check:

   Default PriorityQueue = min heap, need reverseOrder for max heap [OK]

Hint: Default PriorityQueue is min heap; add reverseOrder for max heap [OK]

Common Mistakes:

• Not using reverseOrder comparator
• Changing loop count incorrectly
• Sorting array unnecessarily

5. Given an array arr = {12, 3, 5, 7, 19} and k = 4, which of the following code snippets correctly finds the 4th largest element using a max heap in Java?

hard

A. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int num : arr) maxHeap.add(num);
int kthLargest = 0;
for (int i = 0; i < k; i++) kthLargest = maxHeap.poll();
System.out.println(kthLargest);

B. PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
for (int num : arr) maxHeap.add(num);
int kthLargest = 0;
for (int i = 0; i < k; i++) kthLargest = maxHeap.poll();
System.out.println(kthLargest);

C. PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : arr) {
minHeap.add(num);
if (minHeap.size() > k) minHeap.poll();
}
System.out.println(minHeap.peek());

D. Arrays.sort(arr);
System.out.println(arr[k]);

Solution

1. Step 1: Check each option's approach

   PriorityQueue<Integer> maxHeap = new PriorityQueue<>(); for (int num : arr) maxHeap.add(num); int kthLargest = 0; for (int i = 0; i < k; i++) kthLargest = maxHeap.poll(); System.out.println(kthLargest); uses default min heap, wrong for max heap extraction. PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for (int num : arr) maxHeap.add(num); int kthLargest = 0; for (int i = 0; i < k; i++) kthLargest = maxHeap.poll(); System.out.println(kthLargest); correctly uses max heap with reverseOrder. PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : arr) { minHeap.add(num); if (minHeap.size() > k) minHeap.poll(); } System.out.println(minHeap.peek()); uses min heap to keep k largest elements, which finds kth largest but differently. Arrays.sort(arr); System.out.println(arr[k]); prints wrong index after sorting.

2. Step 2: Verify correct kth largest extraction

   PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for (int num : arr) maxHeap.add(num); int kthLargest = 0; for (int i = 0; i < k; i++) kthLargest = maxHeap.poll(); System.out.println(kthLargest); extracts max element k times from max heap, giving correct 4th largest element.

3. Final Answer:

   Use max heap with reverseOrder and extract k times -> Option A

4. Quick Check:

   Max heap extraction k times = kth largest [OK]

Hint: Use max heap with reverseOrder and extract k times [OK]

Common Mistakes:

• Using min heap without size control
• Incorrect array index after sorting
• Confusing min heap approach with max heap