変更可能なオブジェクトの優先度キュー：それらを実装するための最良の方法は何ですか？

Question

ヒープ/優先度キューにオブジェクトを格納する必要があります。ただし、オブジェクトの順序が変更されるようにオブジェクトが変更される可能性があるため、fixUpまたはfixDownを呼び出す必要があります。これらのメソッドはプライベートであり、Java PriorityQueueはこれをやらせません。私のオプションは：

1. Java PriorityQueueを使用して、オブジェクトを削除してから再挿入します。非常に非効率的で、仕事を倍増させるようです。

2. 独自の優先キューを実装し、Java標準ライブラリの機能を複製するコードを維持します。

これは、これを実行するために推奨される方法/ベストプラクティスですか？ この種の操作は、多くのグラフアルゴリズムを実装するために必要です。 A *なので、Javaはあなたにそれをさせてくれません。

Answer 1

非常に非効率的で、作業を2倍にします。

ただし、半二重優先度キューの実装ではまだO（lg n）です。これを試してそれを測定しなければなりませんか？私は、図書館のものが本当に遅すぎる場合は、私自身のPQの実装を始めます。しかし、もしあなたがそうしたら、OpenJDKでそれをフォークし、そのメソッドのいくつかを "宣伝"するのはどうですか？

Answer 2

私は、 "ホイールを再発明する"とあなた自身の優先度の高いキューインプリメンテーションを書くことを勧めます。

あなたが優先順位の調整を行う必要がある場合は、デルタを管理ラッパーのキューを使用することができ、この（あなたが事の優先権を得ることができると仮定した場合）のようなもの：

class Wrapper implements Comparable<Wrapper> { 

    private final Thing thing; 
    private int delta; 

    public Wrapper (Thing thing) { 
     this.thing = thing; 
    } 

    public void adjustRank(int deltaChange) { 
     delta += deltaChange; 
    } 

    public int compareTo(Wrapper w) { 
     return thing.getRank() + delta - w.thing.getRank() - w.delta; 
    } 
}