4

我将以下代码用于 a PriorityQueue<Node<T>>，其中Node<T>is not Comparable：

final Map<Node<T>, Double> distances = new HashMap<>();

PriorityQueue<Node<T>> queue = new PriorityQueue<Node<T>>(graph
        .getNodes().size(), new Comparator<Node<T>>() {
    @Override
    public int compare(Node<T> o1, Node<T> o2) {
        return distances.get(o1).compareTo(distances.get(o2));
    }
});

稍后在我的代码中，我修改了地图中节点的距离distances.put(...)。如何确保正确更新优先级队列以反映新的排序顺序？

我查看了源代码，PriorityQueue发现它的peek、poll和element方法都只是 get queue[0]，但我不知道如何更新队列的顺序，因为内部方法heapify是private。

4

2 回答 2

1

据我所知，您不能使用默认实现。但是，您可以解决它。这取决于您使用优先级队列的目的：

  1. 仅在节点的优先级增加时更新
  2. 用于在节点的优先级增加和减少时更新

案例 1 是一个更简单的案例，因为 PriorityQueue 已经为您维护了优先级顺序。只需将具有较高优先级的节点添加到队列中，并跟踪之前是否已从优先级队列中弹出节点。（使用布尔数组或哈希表）

当你弹出一个节点时，如果它之前没有被弹出过，你可以保证它是队列中优先级最低的那个，即使你之前已经在队列中添加了多个副本。

情况 2 比较棘手，需要在每个节点中使用一个布尔变量来跟踪它是否“启用”。此外，您需要一个哈希表或数组，以便您可以访问优先级队列中的节点。当您想要更新节点的优先级时，您必须在添加新节点时“禁用”队列中的现有节点。还要跟踪您刚刚添加为“新”现有节点的节点。当您弹出时，只需忽略“禁用”的节点。

至于时间复杂度，添加的摊余成本仍然是 O(log n)。这是因为在“heapify”中更新一个节点在堆中的位置的成本是 O(log n)，它渐近地等于调用 offer。弹出的时间成本将根据添加重复节点与有效节点的比例而增加。

或者，编写您自己的更新优先级队列。

于 2013-09-28T16:37:52.377 回答
0 
if(!priorityQueue.isEmpty()) {
    priorityQueue.add(priorityQueue.remove());
}

应该是触发重新堆化的简单方法。如此处所见

于 2019-03-02T17:21:13.890 回答