我在想是否可能在PriorityQueue中找到值的索引,以查看它在“队列中”的编号。有人知道吗?
我在想是否可能在PriorityQueue中找到值的索引,以查看它在“队列中”的编号。有人知道吗?
普林斯顿大学编写了一个索引优先队列。
algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html
关键思想是构建两个索引映射,将项目与其在优先队列中的位置对应起来。
当您更新优先队列时,还需要更新这两个索引映射。
希望这可以解决您的问题 :-)
PriorityQueue不支持索引。您可以自己为每个项关联一个整数索引。
如果您查看文档中的第一行,您会看到:
An unbounded priority queue based on a priority heap.
你不能有效地使用优先级堆来查找元素的索引。它只知道第一个,当你弹出它时,它会重新计算新的第一个。
这只是一个快速修复方案; 更好的方法是由Ming Li提交的。
可以使用poll()
和peek()
方法解决此问题:
poll()
方法检索顶部元素并将其删除。
假设您想要检查名为pq
的PriorityQueue
中的第k个元素:
for(int i=0; i<k-1; i++){
pq.poll();
}
peek()
方法来查看 PriorityQueue
的最顶端元素:pq.peek();
这将返回PriorityQueue
中最顶部的元素,此例中即第k个位置上的元素。
我有一个 PriorityQueue<Integer[]> queue
,其中索引是数组的第一个元素。因此,我编写了这个方法,在找到元素后实际上从队列中删除它。
由于此方法仅与现有索引一起使用,因此我添加了 orElseThrow
来处理空的 Optional
。
static Integer[] getByIndex(Integer i, PriorityQueue<Integer[]> queue) {
Integer[] node = queue.stream().filter(n -> n[0].equals(i)).findAny().orElseThrow(
() -> new NullPointerException("node " + i + " not found on queue")
);
queue.remove(node);
return node;
}