当 Java PriorityQueue 的元素更改优先级时更新它

Question

我正在尝试使用 PriorityQueue 使用 Comparator 对对象进行排序。

这可以很容易地实现，但是对象类变量（比较器用来计算优先级）在初始插入后可能会发生变化。大多数人提出了删除对象、更新值并再次重新插入的简单解决方案，因为这是优先级队列的比较器投入运行的时候。

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

Answer 1

您必须删除并重新插入，因为队列的工作原理是在插入新元素时将其放置在适当的位置。这比每次从队列中取出时查找最高优先级元素的替代方法要快得多。缺点是插入元素后无法更改优先级。 TreeMap 具有相同的限制（HashMap 也是如此，当插入后其元素的哈希码发生更改时，它也会中断）。

如果你想写一个包装器，你可以将比较代码从入队移动到出队。您不再需要在排队时进行排序（因为如果您允许更改，它创建的顺序无论如何都是不可靠的）。

但这会表现更差，并且如果您更改任何优先级，您希望在队列上同步。由于更新优先级时需要添加同步代码，因此您不妨只出队和入队（在这两种情况下都需要对队列的引用）。

Answer 2

我不知道是否有 Java 实现，但如果您要大量更改键值，则可以使用 Fibonnaci 堆，它具有 O(1) 摊销成本减少键值堆中的条目，而不是普通堆中的 O(log(n))。

Answer 3

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

为了证明这一点，让我们考虑下面的 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 4

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

1）删除并放回

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

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

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

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

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

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

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

注意：在上面的解释中，优先级是指您的比较器中使用的所有变量。您的项目还需要实现equals和hashcode，以及两者。方法不应使用优先级变量。

Answer 5

这在很大程度上取决于您是否可以直接控制值何时发生变化。

如果您知道值何时发生变化，则可以删除并重新插入（实际上这相当昂贵，因为删除需要对堆进行线性扫描！）。
此外，对于这种情况，您可以使用 UpdatableHeap 结构（尽管 Java 中没有）。本质上，这是一个跟踪哈希图中元素位置的堆。这样，当某个元素的优先级发生变化时，就可以修复堆。第三，您可以寻找具有相同功能的斐波那契堆。

根据您的更新速率，每次线性扫描/快速排序/快速选择也可能有效。特别是如果您的更新比拉取的更新多得多，那么这就是正确的选择。如果您有批量更新和批量拉取操作，则 QuickSelect 可能是最好的选择。

Answer 6

要触发 reheapify，请尝试以下操作：

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

Answer 7

我已经尝试过并且到目前为止有效的方法是查看您要更改的对象的引用是否与 PriorityQueue 的头部相同，如果是，则您 poll()，更改然后重新插入;否则你可以在不轮询的情况下进行更改，因为当轮询头部时，堆无论如何都会被堆化。

缺点：这会改变具有相同优先级的对象的优先级。

Answer 8

除了围绕 PriorityQueue 创建一个包装类来执行此操作之外，还有更好的方法吗？

这取决于“更好”的定义和包装器的实现。

如果包装器的实现是使用 PriorityQueue 的 .remove(...) 和 .add(...) 重新插入值方法，
需要指出的是，.remove(...) 的运行时间为 O(n)。
根据堆的实现，
更新值的优先级可以在 O(log n) 甚至 O(1) 时间内完成，
因此，这个包装建议可能达不到普遍的期望。

如果您想最大限度地减少实施工作量，
以及任何自定义解决方案的错误风险，
那么执行重新插入的包装器看起来既简单又安全。

如果您希望实现速度快于O(n)，
那么你有一些选择：

1. 自己实现一个堆。 维基百科条目描述了多个变体及其属性。这种方法很可能会获得最佳性能，同时您自己编写的代码越多，出现错误的风险就越大。

2. 实现不同类型的包装器：通过将条目标记为已删除来处理更新优先级，并添加具有修改优先级的新条目。
   这相对容易做到（代码较少），请参见下文，尽管它有自己的注意事项。

我在 Python 文档中遇到了第二个想法，
并应用它在 Java 中实现可重用的数据结构（请参阅底部的警告）：

public class UpdatableHeap<T> {

  private final PriorityQueue<Node<T>> pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.priority));
  private final Map<T, Node<T>> entries = new HashMap<>();

  public void addOrUpdate(T value, int priority) {
    if (entries.containsKey(value)) {
      entries.remove(value).removed = true;
    }

    Node<T> node = new Node<>(value, priority);
    entries.put(value, node);
    pq.add(node);
  }

  public T pop() {
    while (!pq.isEmpty()) {
      Node<T> node = pq.poll();
      if (!node.removed) {
        entries.remove(node.value);
        return node.value;
      }
    }

    throw new IllegalStateException("pop from empty heap");
  }

  public boolean isEmpty() {
    return entries.isEmpty();
  }

  private static class Node<T> {
    private final T value;
    private final int priority;
    private boolean removed = false;

    private Node(T value, int priority) {
      this.value = value;
      this.priority = priority;
    }
  }
}

请注意一些警告：

• 标记为已删除的条目将保留在内存中，直到被弹出
  • 这在更新非常频繁的用例中可能是不可接受的
• 围绕实际值的内部 Node 会产生额外的内存开销（每个条目恒定）。还有一个内部 Map，将优先级队列中当前的所有值映射到其 Node 包装器。
• 由于值在映射中使用，因此用户在使用映射时必须注意通常的注意事项，并确保具有适当的 equals 和 hashCode 实现。