在其元素更改优先级时更新Java PriorityQueue

Question

我正在尝试使用a PriorityQueue来命令对象Comparator.

这可以很容易地实现,但是对象类变量(比较器计算优先级)可能在初始插入后发生变化.大多数人都提出了删除对象,更新值并再次重新插入的简单解决方案,因为这是优先级队列的比较器付诸行动的时候.

除了在PriorityQueue周围创建一个包装类之外,还有更好的方法吗？

Answer 1

您必须删除并重新插入,因为队列的工作方式是在插入新元素时将它们放入适当的位置.这比每次退出队列时找到最高优先级元素的选择要快得多.缺点是在插入元素后无法更改优先级.TreeMap具有相同的限制(HashMap也是如此,当插入后其元素的哈希码发生变化时,它也会中断).

如果要编写包装器,可以将比较代码从enqueue移动到dequeue.您不需要再排队入队时间(因为如果允许更改,它创建的顺序无论如何都不可靠).

但是这会表现得更糟,如果您更改任何优先级,您希望在队列上进行同步.由于您需要在更新优先级时添加同步代码,因此您可能只是出列并入队(在两种情况下都需要对队列的引用).

Answer 2

我不知道是否有Java实现,但如果您正在更改键值,则可以使用Fibonnaci堆,其具有O(1)摊销成本以减少堆中条目的键值,而不是比普通堆中的O(log(n)).

Answer 3

无需自己重新实现优先级队列（因此​​仅使用utils.PriorityQueue），您基本上有两种主要方法：

1) 取出并放回原处

删除元素，然后以新的优先级将其放回原处。上面的答案对此进行了解释。删除一个元素的时间复杂度为 O(n)，因此这种方法非常慢。

2）使用Map并将过时的项目保留在队列中

保留HashMap项目 -> 优先级。映射的键是项目（没有优先级），映射的值是优先级。

使其与 PriorityQueue 保持同步（即每次从队列中添加或删除项目时，相应地更新映射）。

现在，当您需要更改某个项目的优先级时，只需将相同的项目添加到具有不同优先级的队列中（当然还要更新地图）。当您从队列中轮询某个项目时，请检查其优先级是否与地图中的优先级相同。如果没有，则放弃它并再次轮询。

如果您不需要经常更改优先级，则第二种方法更快。您的堆会更大，您可能需要轮询更多次，但您不需要找到您的项目。“更改优先级”操作将为O(f(n)log n*)，其中f(n)是每个项目的“更改优先级”操作数，n*是堆的实际大小（即 n*f( n))。

我相信如果f(n)是 O(n/logn)（例如 f(n) = O(sqrt(n))，这比第一种方法更快。

注意：在上面的解释中，优先级是指比较器中使用的所有变量。此外，您的项目需要实现equals和hashcode，并且这两种方法都不应该使用优先级变量。

Answer 4

您可以实施的一种简单解决方案是将该元素再次添加到优先级队列中。它不会改变您提取元素的方式，尽管它会占用更多空间，但这也不会影响您的运行时间。

为了证明这一点，让我们考虑下面的 dijkstra 算法

public int[] dijkstra() {
int distance[] = new int[this.vertices];
int previous[] = new int[this.vertices];
for (int i = 0; i < this.vertices; i++) {
    distance[i] = Integer.MAX_VALUE;
    previous[i] = -1;
}
distance[0] = 0;
previous[0] = 0;
PriorityQueue<Node> pQueue = new PriorityQueue<>(this.vertices, new NodeComparison());
addValues(pQueue, distance);
while (!pQueue.isEmpty()) {
    Node n = pQueue.remove();
    List<Edge> neighbours = adjacencyList.get(n.position);
    for (Edge neighbour : neighbours) {
        if (distance[neighbour.destination] > distance[n.position] + neighbour.weight) {
            distance[neighbour.destination] = distance[n.position] + neighbour.weight;
            previous[neighbour.destination] = n.position;
            pQueue.add(new Node(neighbour.destination, distance[neighbour.destination]));
        }
    }
}
return previous;

}

在这里，我们的兴趣是一致的， pQueue.add(new Node(neighbour.destination, distance[neighbour.destination])); 我不会通过删除并再次添加来更改特定节点的优先级，而只是添加具有相同值但不同优先级的新节点。现在在提取时，我将始终首先获取此节点，因为我在这里实现了最小堆，并且值大于此（优先级较低）的节点总是在之后被提取，这样所有相邻节点将在较不优先时已经放松元素将被提取。

Answer 5

这取决于您是否可以直接控制值何时发生变化.

如果您知道值何时更改,您可以删除并重新插入(实际上这相当昂贵,因为删除需要在堆上进行线性扫描!).此外,您可以使用UpdatableHeap结构(尽管不是库存java).本质上,这是一个跟踪hashmap中元素位置的堆.这样,当元素的优先级发生变化时,它可以修复堆.第三,你可以寻找一个同样的Fibonacci堆.

根据您的更新速率,每次线性扫描/快速排序/ QuickSelect也可能有效.特别是如果你有比pulls 更多的更新,这是要走的路.如果您有批量更新然后批量拉动操作,QuickSelect可能是最好的.