java - 通过键查找 PriorityQueue 中的元素

Question

假设我得到了一些 key 。我想要找到的是优先级队列中的一个元素，它的键等于或大于给定的键。

显然，我希望它在 O(logn) 中完成。我几乎可以肯定 Java 提供了这样的方法但找不到它(在官方文档中查看)

Answer 1

没有这样的方法。

优先级队列的底层实现是最小堆(也可以配置为最小堆)。所以对于具有最大堆属性的优先级队列，当你检查 peek 元素时(即 O(1) 操作)，它将返回最大元素。轮询出来后，将执行heapify-ing，下一个top元素将是第二大元素。复杂度为 O(logn)。所以，如果你想让所有的键都大于或等于给定的键，你需要从最大堆优先级队列中不断轮询，直到顶部元素小于给定的键。在最坏的情况下，这可能是 O(nlogn)。

同样在这些操作之后，队列结构将被改变，因为一些键已经被轮询。因此，在下一次操作之前，您必须通过重新推送轮询键来恢复队列的状态，这也是 O(nlogn)。

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;
}