Why is my PriorityQueue implementation slower than sorting for the kth largest integer problem?-CodePudding

I implemented two solutions to the kth largest integer problem, where we are given an array of integers and have to return the kth largest integer in the array. The first one used a PriorityQueue, and has a runtime complexity of O(n). The second simply sorted the array and returned the kth element, and has a runtime complexity of O(nlogn).

However when I benchmarked both implementations against a large array the sort method was significantly faster than the PriorityQueue method for many different values of k, for example when k is half the size of the array.

What could I be doing wrong in my PriorityQueue implementation that is causing it to be slower than the sort implementation?

Here is the code I have:

import java.util.PriorityQueue;
import java.util.Random;

public class KthLargestElement {

    public static void main(String[] args) {
        int n = 100000000;
        int k = n/2;
        int[] numbers = intsInRange(n, 0, n*100);

        long start = System.currentTimeMillis();
        kthLargestPriorityQueueMethod(numbers, k);
        System.out.println("priority queue method time in seconds = "   (double)(System.currentTimeMillis() - start)/1000.0);

        start = System.currentTimeMillis();
        kthLargestSortMethod(numbers, k);
        System.out.println("sort method time in seconds = "   (double)(System.currentTimeMillis() - start)/1000.0);
    }

    private static int kthLargestSortMethod(int[] numbers, int k) {
        Arrays.sort(numbers);
        return numbers[numbers.length - k];
    }

    private static int kthLargestPriorityQueueMethod(int[] numbers, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(int i : numbers){
            q.offer(i);

            if(q.size() > k){
                q.poll();
            }
        }

        return q.peek();
    }

    private static int[] intsInRange(int size, int lowerBound, int upperBound) {
        Random random = new Random();
        int[] result = new int[size];
        for (int i = 0; i < size; i  ) {
            result[i] = random.nextInt(upperBound - lowerBound)   lowerBound;
        }
        return result;
    }
}

And here is the output I get on my computer:

priority queue method time in seconds = 78.194
sort method time in seconds = 9.864

CodePudding user response：

That is because you are sorting the array only once in your sort method which gives you a time complexity of O(n*log(n)).

Now for your PriorityQueue implementation the average time complexity is O(n*log(n)) for a large value of k, where log(n) is the average time complexity of insertion for a pq.

Now you are not taking into account jvm warmup which might be adding more time to the result. For more info on jvm warmup check here: https://www.baeldung.com/java-jvm-warmup

CodePudding user response：

The bug is in your understanding, not your code.

The priority queue approach is O(n log(k)) running time with constants that aren't as good as the sort. So when log(k) = log(n) O(1), then it is no surprise that the priority queue can be slower.

You can get an improvement by only bothering with the offer/poll when the the current element won't be the one polled. This improvement will be more significant if k is small relative to n.