Find an element in a PriorityQueue by key

Question

Suppose I've been given some key. What I'd like to find is an element in the priority queue such that it's key equal or greater than the given key.

Obviously, I want to it to be done in O(logn). I'm almost certain Java offers such method yet couldn't find it (looked in the official docs)

Answer 1

There is no such method.

The underlying implementation of priority queue is min heap (it can be configured to act as min heap as well). So for a priority queue with max heap property, when you check the peek element (which is O(1) operation), it will return the maximum element. After polling it out, heapify-ing will be performed and the next top element will be the second maximum. This heapify-ing in of O(logn) complexity. So, if you want to get all keys greater or equal to a given key, you need to keep polling from max-heap priority queue until top element is less than given key. And in worst case, this can be O(nlogn).

Also after these operations, the queue structured will be altered as some of the keys had been polled. So before next operation, you have to restore your queue's state by re-pushing the polled keys which will be O(nlogn) too.

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder())

List<Integer> keysGreaterOrEqualTo(Integer key) {
    List<Integer> keys = new ArrayList<>();
    while(!queue.isEmpty() && queue.peek() >= key) {
        keys.add(queue.poll());
    }
    return keys;
}