通过键查找 PriorityQueue 中的元素

Question

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

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

Answer 1

没有这种方法。

优先级队列的底层实现是最小堆（也可以配置为最小堆）。所以对于最大堆属性的优先级队列，当你检查peek元素（即O(1)操作）时，它会return最大元素。轮询出来后，将执行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;
}

Answer 2

Java 优先级队列有 contains() 方法，如果在优先级队列中找到键，则该方法 returns 为真。参考 - Reference

要查找大于或等于的键，您可以实现自己的自定义方法。如：

int searchkey = 5, foundKey = 0;

While(!pq.isEmpty()){
  foundKey = pq.poll();   
  if(foundKey == searchKey || foundKey > searchKey)
    break;
}
System.out.println(foundKey == searchKey || foundKey > searchKey ? foundKey : -1);

Answer 3

有一种非破坏性的方法可以做到这一点。您可以使用 iterator 进行搜索，而不是从队列中移除内容直到找到符合条件的内容。

了解迭代器不会 return 任何特定顺序的项目，因此如果您想要大于或等于某个值的最小项目，您仍然必须迭代整个集合。

这个的复杂度显然是O(n)。已接受答案中描述的破坏性技术的复杂性为 O(k log n)，其中 k 是小于您要搜索的项目的数量。在最坏的情况下，k=n，算法是 O(n log n).

Answer 4

我认为您最好改用 TreeSet，特别是 tailSet 方法。它可以像优先级队列一样使用，它也是 N log N.

通过键查找 PriorityQueue 中的元素

Find an element in a PriorityQueue by key

java

priority-queue

data-structures