Kth Largest Element Using Max Heap in DSA Java - Build from Scratch

Kth Largest Element Using Max Heap

📖 Scenario: You are working on a program that helps find the kth largest number from a list of numbers. This is useful when you want to quickly find a specific big number without sorting the entire list.

🎯 Goal: Build a Java program that uses a max heap to find the kth largest element in a list of integers.

📋 What You'll Learn

Create an integer array called numbers with the exact values: 12, 3, 5, 7, 19

Create an integer variable called k and set it to 3

Use a PriorityQueue as a max heap to find the kth largest element

Print the kth largest element

💡 Why This Matters

🌍 Real World

Finding the kth largest element is useful in scenarios like finding the top scores, highest sales, or largest values quickly without sorting the entire dataset.

💼 Career

Understanding heaps and priority queues is important for software engineers working on performance-critical applications, data processing, and algorithm optimization.

1

Create the numbers array

Create an integer array called numbers with these exact values: 12, 3, 5, 7, 19.

DSA Java

// Create the integer array numbers with values 12, 3, 5, 7, 19
// Your code here

Hint

Use int[] numbers = {12, 3, 5, 7, 19}; to create the array.

2

Set the value of k

Create an integer variable called k and set it to 3.

DSA Java

int[] numbers = {12, 3, 5, 7, 19};
// Create the integer variable k and set it to 3
// Your code here

Hint

Use int k = 3; to create the variable.

3

Use a max heap to find the kth largest element

Create a PriorityQueue<Integer> called maxHeap that works as a max heap using a comparator. Add all elements from numbers to maxHeap. Then remove elements from maxHeap exactly k - 1 times.

DSA Java

import java.util.PriorityQueue;
import java.util.Collections;

int[] numbers = {12, 3, 5, 7, 19};
int k = 3;

// Create maxHeap as a PriorityQueue with reverse order comparator
// Add all numbers to maxHeap
// Remove k-1 elements from maxHeap
// Your code here

Hint

Use PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); to create a max heap.

Use a for-each loop to add elements.

Use a for loop to remove k - 1 elements.

4

Print the kth largest element

Print the element at the top of maxHeap using System.out.println.

DSA Java

import java.util.PriorityQueue;
import java.util.Collections;

int[] numbers = {12, 3, 5, 7, 19};
int k = 3;

PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder());
for (int num : numbers) {
    maxHeap.add(num);
}
for (int i = 0; i < k - 1; i++) {
    maxHeap.poll();
}

// Print the kth largest element
// Your code here

Hint

Use System.out.println(maxHeap.peek()); to print the kth largest element.

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