java - 如何触发 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(...) 修改了 map 中节点的距离。 .如何确保优先级队列得到正确更新以反射(reflect)新的排序顺序？

我看过 source对于 PriorityQueue并看到它的 peek , poll , 和 element方法都只是得到 queue[0] , 但我不知道如何更新队列的顺序，作为内部方法 heapify是private .

Answer 1

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

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

情况 1 是一个简单得多的情况，因为 PriorityQueue 已经为您维护了优先级顺序。只需将优先级较高的节点加入队列，并跟踪之前是否有节点从优先级队列中弹出。 (使用 boolean 数组或哈希表)

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

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

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

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