如何在优先队列中查找元素的索引？（Java）

Question

我在想是否可能在PriorityQueue中找到值的索引，以查看它在“队列中”的编号。有人知道吗？

- AndrewP

Answer 1

普林斯顿大学编写了一个索引优先队列。

algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html

关键思想是构建两个索引映射，将项目与其在优先队列中的位置对应起来。

当您更新优先队列时，还需要更新这两个索引映射。

希望这可以解决您的问题 :-)

- Meng Zhang

---

链接现在位于https://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html。 - alex

Answer 2

PriorityQueue不支持索引。您可以自己为每个项关联一个整数索引。

- Piyush Mattoo

---

是的，请查看代码：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/PriorityQueue.java#PriorityQueue - roottraveller

Answer 3

如果您查看文档中的第一行，您会看到：

An unbounded priority queue based on a priority heap. 

你不能有效地使用优先级堆来查找元素的索引。它只知道第一个，当你弹出它时，它会重新计算新的第一个。

- Petar Ivanov

Answer 4

这只是一个快速修复方案； 更好的方法是由Ming Li提交的。

可以使用poll()和peek()方法解决此问题： poll()方法检索顶部元素并将其删除。

假设您想要检查名为pq的PriorityQueue中的第k个元素：

for(int i=0; i<k-1; i++){
        pq.poll();
    }

接下来，我们使用 peek() 方法来查看 PriorityQueue 的最顶端元素：

pq.peek();

这将返回PriorityQueue中最顶部的元素，此例中即第k个位置上的元素。

- Koushik Joshi

Answer 5

我有一个 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;
}

- rado