79

我正在尝试使用 aPriorityQueue来订购使用 a 的对象Comparator。

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

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

4

8 回答 8

55

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

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

但这会执行得更糟，如果您更改任何优先级，您希望在队列上同步。由于在更新优先级时需要添加同步代码，所以最好只出队和入队（这两种情况都需要对队列的引用）。

于 2009-12-09T02:47:03.170 回答
13

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

于 2009-12-09T03:58:28.253 回答
7

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

为了证明这一点，让我们考虑下面的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])); 我不会通过删除特定节点并再次添加来更改特定节点的优先级，而只是添加具有相同值但优先级不同的新节点。现在在提取的时候，我总是首先得到这个节点，因为我在这里实现了最小堆，并且值大于这个（优先级较低）的节点总是在之后被提取，这样所有相邻节点都将在较少先验时被放松元素将被提取。

于 2019-01-05T06:29:30.013 回答
5

这在很大程度上取决于您是否可以直接控制值何时更改。

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

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

于 2012-12-24T00:18:47.807 回答
3

要触发 reheapify 试试这个：

if(!priorityQueue.isEmpty()) {
    priorityQueue.add(priorityQueue.remove());
}
于 2018-04-01T15:54:14.343 回答
2

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

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

于 2018-05-20T05:32:58.370 回答
2

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

1) 取下并放回

移除元素，然后以新的优先级将其放回原处。这在上面的答案中得到了解释。删除一个元素是 O(n) 所以这种方法很慢。

2）使用地图并在队列中保留陈旧的项目

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

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

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

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

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

注意：在上面的解释中，优先级是指 Comparator 中使用的所有变量。此外，您的项目需要实现equalsand hashcode，并且这两种方法都不应该使用优先级变量。

于 2021-06-06T12:13:33.807 回答
0

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

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

PriorityQueue如果包装器的实现是使用's.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围绕实际值的内部是额外的内存开销（每个条目的常量）。还有一个 internal Map，将当前优先级队列中的所有值映射到它们的Node包装器。
  • 由于这些值是在地图中使用的，因此用户在使用地图时必须注意通常的注意事项，并确保有适当equals的hashCode实现。
于 2022-02-06T17:20:15.347 回答