in Java, How do I peek() the top k elements in a PriorityQueue ?
algorithm, data-structures, java
Solution
It's not possible to do it in constant time. If your data is already in a `PriorityQueue`, removing the top k elements one by one is the best you can do. Each remove costs you `O(log(n))` but you have also figured that one out, hence the question.
However, if you are not forced to use a `PriorityQueue`, then you can do a partial sort on a list and retrieve the top k elements. The asymptotic complexity of a partial sort is `O(n*log(k))`. It can be executed faster than the `PriorityQueue` approach if we also take into account the cost of setting up the priority queue, see Selecting top k items from a list efficiently in Java / Groovy (select the top 5 elements from a list of 10 million, PriorityQueue 300ms vs. partial sort 170ms).
Problem
I see in the documentation, that PriorityQueue.peek() gives me access to the head of the queue in O(1), but what if I need access to the k top elements in the queue ? I would use `poll()` k times, but that takes O(log(N)) , is there a way to do it in constant time ?