如何触发PriorityQueue的堆积？

Question

我正在使用以下代码为PriorityQueue<Node<T>>，其中Node<T>不是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(...)修改地图中节点的距离。如何确保优先级队列正确更新以反映新的排序顺序？

我看了source为PriorityQueue看到它的peek，poll和element方法都得到queue[0]，但我不知道如何更新队列的顺序，因为内部方法heapify是private。

Answer 1

据我所知，你无法使用默认实现。但是，您可以解决它。这取决于您使用优先级队列的内容：

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

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

当您弹出节点时，如果之前没有弹出节点，则可以保证它是队列中具有最低优先级的节点，即使您先前已将多个副本添加到队列中也是如此。

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

至于时间复杂度，摊销成本仍然是O（log n）用于添加。这是因为在“heapify”中更新节点在堆中的位置的成本是O（log n），它渐近地等于调用offer。 pop的时间成本将增加，具体取决于添加重复节点与有效节点的比率。

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

Answer 2

if(!priorityQueue.isEmpty()) {
    priorityQueue.add(priorityQueue.remove());
}

应该是一种触发重新堆积的简单方法。正如看到here