Solution: A Max-Heap

Sorting worked, but we ordered all $n$ elements when we wanted only one of them. A heap gives us the highest-priority element without sorting the rest.

A priority queue serves its highest-priority element first. If we make largest mean highest priority, then the first element out is the largest, the next is the second largest, and so on. So add the whole array to a max-heap, remove $k - 1$ times, and the next call to peek returns the kth largest.

ArrayHeap serves the smallest element first by default. To make the largest element the highest priority, we pass it a comparator that reverses the order. Comparator.reverseOrder() is a library method that returns a comparator reversing the natural ordering.

public static int findKthLargestMaxHeap(int[] numbers, int k) {
  Comparator<Integer> largestFirst = Comparator.reverseOrder();
  PriorityQueue<Integer> heap = new ArrayHeap<>(largestFirst);
  for (int number : numbers) {
    heap.add(number);
  }
  for (int i = 1; i < k; i++) {
    heap.remove();  // drop the largest still in the heap
  }
  return heap.peek();
}

Let’s trace it on numbers = [3, 1, 5, 2, 4] with k = 2. First we add all five elements. Because it is a max-heap, peek returns the largest, 5. The diagrams show the contents largest-first so that peek and the removes are easy to follow; the heap’s array is not in this order.

┌───┬───┬───┬───┬───┐
│ 5 │ 4 │ 3 │ 2 │ 1 │   size = 5
└───┴───┴───┴───┴───┘
  ▲
 peek → 5   (max)

We want the second largest, so we remove once. That takes out 5, and peek now returns the largest of what remains, 4:

┌───┬───┬───┬───┐
│ 4 │ 3 │ 2 │ 1 │   size = 4
└───┴───┴───┴───┘
  ▲
 peek → 4   (max)

The $n$ adds cost $O (n lo g n)$ , and the $k - 1$ removes cost $O (k lo g n)$ , so the whole solution is $O (n lo g n)$ , the same as sorting. But the heap in the first picture held all five elements, when only the two largest mattered. Both the memory we use and the work of filling the heap grow with the size of the whole array, not with k.