java - 如何在 PriorityQueue 中找到项目的索引？（爪哇）

Question

我想知道是否可以在 PriorityQueue 中找到值的索引。只是为了看看它是“在线”的数字。有人知道吗？

Answer 1

有一个普林斯顿写的索引优先级队列。

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

关键思想是在项目与其在优先级队列中的位置之间建立两个索引映射。

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

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

Answer 2

PriorityQueue 不支持索引。您可以自己将整数索引与每个项目相关联。

Answer 3

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

An unbounded priority queue based on a priority heap. 

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

Answer 4

这是一个快速修复；更好的方法是李明提出的方法。

可以使用poll()andpeek()方法解决这个问题：该poll()方法检索最顶层的元素并将其删除。

假设您要检查PriorityQueuenamed中的第 k 个元素pq：

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

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

pq.peek();

这将返回 的最顶部元素PriorityQueue，在这种情况下，它将是第 k 个位置的元素。

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