Javaプライオリティキュー

Question

Javaに組み込まれたプライオリティキューを使用してグラフの読み込みとソートを行うと、各繰り返しで最小エッジが削除されます。

Answer 1

まず、プライオリティキューのためのコンパレータを作成します。

class MinHeapComparator implements Comparator<Integer> { 
    @Override 
    public int compare(Integer one, Integer two) { 
    return mDistances[one] - mDistances[two];//... 
    } 
    } 

これは私が書いた最短経路アルゴリズムからです。 mDistancesは、ソースから頂点までの距離です。コンパレータを変更して、好きなように比較することができます。

コンパレータのドキュメントから：「順序の2つの引数を比較します。最初の引数が2番目の引数よりも小さい、負の整数または正の整数を返します。ここ

完全なドキュメント：http://download.oracle.com/javase/1.5.0/docs/api/java/util/Comparator.html

第二に、プライオリティキューにアイテムを追加します。私は通常、頂点オブジェクトを含む配列を持つグラフを作成します。各オブジェクトは、隣接する頂点のリストを含んでいます。だから、私の場合は、インデックスを優先度キューに追加して頂点を表現するだけです。コンパレータには、頂点に関係なく何でも行うロジックを含めることができます。 PriorityQueue.add（）はアイテムを追加します。

第三に、コンパレータでプライオリティキューをインスタンス化：

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(numberItems, new MinHeapComparator()); 

第四に、ヒープ上の最上位項目を抽出するためにPriorityQueue.poll（）を呼び出します。コンパレータは、ヒープの先頭にあるアイテムを特定するために使用されます。