如何触发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(...)修改了地图上节点的距离。如何确保优先队列正确更新以反映新的排序顺序？

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

- wchargin

---

请查看https://dev59.com/-HRB5IYBdhLWcg3wHkPi。 - Melih Altıntaş

Answer 1

据我所知，使用默认实现是无法做到的。但是您可以绕过它。这取决于您使用优先队列的目的：

1. 仅在节点优先级提高时进行更新
2. 在节点优先级提高和降低时均进行更新

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

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

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

关于时间复杂度，添加的摊销成本仍将为O(log n)。这是因为在“堆化”中更新节点位置的成本为O(log n)，与调用offer渐近相等。pop的时间成本将取决于添加重复节点与有效节点的比率。

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

- nitegazer2003

Answer 2

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

应该有一种简单的方法来触发重新堆化。 如此处所示

- aneesh joshi