Problem: The Kth Largest Element

Let’s use the binary heap to find the kth largest element in an array.

Here is the method signature:

public static int findKthLargest(int[] numbers, int k) {

}

Example 1:

For numbers = [3, 1, 5, 2, 4] and k = 2, the values in sorted order are 1, 2, 3, 4, 5. The largest is 5 and the second largest is 4, so we return 4.

Example 2:

For numbers = [3, 1, 5, 2, 4] and k = 1, the kth largest is just the largest element, 5.

Example 3:

For numbers = [4, 4, 5, 2] and k = 3, the sorted values are 2, 4, 4, 5. The largest is 5, the second largest is 4, and the third largest is the other 4. Equal values count separately, so we return 4, not 2.

Let’s assume numbers is not empty and 1 <= k <= numbers.length.

Try the most direct solution first, then look for one that does less work.