Max heap myths around finding the kth largest element from an array

You might have heard about this problem already either in an interview or in a casual discussion with colleagues or friends. Let’s go into the topic.

Input: nums = [3,2,1,5,6,4] and k = 2
Output: 5

Consider we have an array of integers. Whenever you are asked to write a program to find the kth largest element from an array of integers.

We immediately think of sorting the array and returning the element at index length - k. It may be a Brute-force algorithm but park it aside for some time. See the below code for reference.

Arrays.sort(nums);
max = nums[nums.length - k];

Generally the above is not recommended since sorting in the worst case takes quadratic time(O(n²)).

So, then how should we minimize the complexity. Programmers tend to think using heap data structure(max-heap) which keeps the track of maximum numbers at any given point of time. As soon as we build the max-heap with all the given numbers, we go on to remove the first k numbers from the heap therefore we get the kth maximum but remember this is not in place(we are using additional memory for heap here) and it takes about O(n log n) to construct the max-heap and to get the kth maximum O(k log n). See the below code for reference.

// construction of max heap
PriorityQueue<Integer> maxHeap = new PriorityQueue(Collections.reverseOrder());

for (int i = 0; i < nums.length; i++){
    maxHeap.add(nums[i]);
}

int max;
// Remove the top k-1 roots of max heap
for (int i = 0; i < k -1; i++){
    maxHeap.remove();
}
// k th element of heap
max = maxHeap.remove();

I have run a performance run about 10 times to see which one is faster on both these algorithms with about 100 million integers in an array to find the kth maximum. For the first algorithm, it just took about 12 milliseconds on average and for the latter(max-heap) it took about 3500 milliseconds.

But still, ironically interviewers get convinced only when you talk about the latter. It happened to me in a couple of interviews.

I hope that you will find this article helpful. Feel free to comment, suggest or share your opinion.