79

PriorityQueueを使用してオブジェクトを注文しようとしていComparatorます。

これは簡単に実現できますが、オブジェクトクラス変数（コンパレータが優先度を計算するため）は、最初の挿入後に変更される可能性があります。ほとんどの人は、オブジェクトを削除し、値を更新して再挿入するという簡単な解決策を提案しています。これは、優先キューのコンパレータが動作するときです。

これを行うために、PriorityQueueの周りにラッパークラスを作成する以外のより良い方法はありますか？

4

8 に答える 8

55

キューは、挿入時に新しい要素を適切な位置に配置することで機能するため、削除して再挿入する必要があります。これは、キューから引き出すたびに最も優先度の高い要素を見つけるという代替手段よりもはるかに高速です。欠点は、要素が挿入された後は優先度を変更できないことです。TreeMapにも同じ制限があります（HashMapも同様です。これは、挿入後に要素のハッシュコードが変更されたときにも壊れます）。

ラッパーを作成する場合は、比較コードをエンキューからデキューに移動できます。エンキュー時にソートする必要はもうありません（変更を許可した場合、作成される順序は信頼できないため）。

ただし、これはパフォーマンスが低下するため、優先順位のいずれかを変更した場合は、キューで同期する必要があります。優先度を更新するときに同期コードを追加する必要があるため、デキューしてエンキューするだけでもかまいません（どちらの場合もキューへの参照が必要です）。

于 2009-12-09T02:47:03.170 に答える
13

Java実装があるかどうかはわかりませんが、キー値を大幅に変更する場合は、O（1）償却コストを持つFibonnaciヒープを使用して、ヒープ内のエントリのキー値を減らすことができます。通常のヒープのようにO（log（n））よりも。

于 2009-12-09T03:58:28.253 に答える
7

実装できる簡単な解決策の1つは、その要素を優先キューに再度追加することです。より多くのスペースを消費しますが、要素を抽出する方法は変わりませんが、実行時間に影響を与えるほど多くはありません。

これを証明するために、以下のダイクストラアルゴリズムを考えてみましょう。

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の在庫はありません）を使用できます。基本的に、これはハッシュマップ内の要素の位置を追跡するヒープです。このようにして、要素の優先度が変更されたときに、ヒープを修復できます。第三に、同じことをするフィボナッチヒープを探すことができます。

更新レートによっては、毎回リニアスキャン/クイックソート/クイックセレクトも機能する場合があります。pull特に、 sよりもはるかに多くの更新がある場合は、これが最適な方法です。更新のバッチがあり、次にプル操作のバッチがある場合は、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）、基本的に2つの主要なアプローチがあります。

1）取り外して元に戻す

要素を削除してから、新しい優先度で元に戻します。これは上記の回答で説明されています。要素の削除はO（n）であるため、このアプローチは非常に時間がかかります。

2）マップを使用して、古いアイテムをキューに入れます

HashMapアイテム->優先度を維持します。マップのキーはアイテム（優先度なし）であり、マップの値は優先度です。

PriorityQueueとの同期を維持します（つまり、キューにアイテムを追加または削除するたびに、それに応じてマップを更新します）。

これで、アイテムの優先度を変更する必要がある場合は、同じアイテムを異なる優先度でキューに追加するだけです。キューからアイテムをポーリングするときは、その優先度がマップ内と同じであるかどうかを確認してください。そうでない場合は、それを捨てて、もう一度ポーリングします。

優先順位を頻繁に変更する必要がない場合は、この2番目のアプローチの方が高速です。ヒープが大きくなり、より多くの回数ポーリングする必要があるかもしれませんが、アイテムを見つける必要はありません。'change priority'操作はO（f（n）log n *）であり、f（n）はアイテムごとの'change priority'操作の数であり、n *はヒープの実際のサイズ（n * f（ n））。

f（n）がO（n / logn）（たとえば、f（n）= O（sqrt（n））の場合、これは最初のアプローチよりも高速であると思います。

注：上記の説明では、優先順位によって、コンパレーターで使用されるすべての変数を意味します。また、アイテムはとを実装する必要がequalsあり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のドキュメントで2番目のアイデアに出くわし、それを適用して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ます。
于 2022-02-06T17:20:15.347 に答える