java - Java のプライオリティ キュー

Question

2つのパラメータを指定できますか? たとえば、文字列と対応する整数を優先キーに追加したいとします。次に、その整数で並べ替えます。文字列または整数のいずれかを追加する方法は知っていますが、両方を追加する方法はわかりません。誰かが私を正しい方向に向けて、私がこれを正しい方法で行っているかどうかを教えてください。

Answer 1

これには 2 つの方法があります。いずれにせよ、文字列 (必要な値) と整数 (優先順位) の両方を保持するカスタム オブジェクトを作成する必要があります。

最初の解決策は、このデータ オブジェクトにComparableを実装させることです。

class Data implements Comparable<Data> {
  private final String message;
  private final int priority;

  public Data(String message, int priority) {
    this.message = message;
    this.priority = priority;
  }

  @Override
  int compareTo(Data other) {
    return Integer.valueOf(priority).compareTo(other.priority);
  }

  // also implement equals() and hashCode()
}

その後、あなたがするとき

PriorityQueue<Data> queue = new PriorityQueue<Data>();

compareToキューは、メソッドで定義された順序でアイテムを並べ替えます。

このソリューションの問題は、順序付けを整数のみにしたい場合、equalsメソッドとメソッドのいずれかcompareToが一貫していないか、equalsメソッドが正しくないことです。

より良い解決策は、 Comparatorを取るPriorityQueueコンストラクターを使用することです。この場合、実装する必要はありません。順序を定義するが必要なだけです。DataComparableComparator

public final class OrderDataByPriority implements Comparator<Data> {
  public static final OrderDataByPriority INSTANCE = new OrderDataByPriority();

  private OrderDataByPriority() {}

  @Override
  public int compare(Data data1, Data data2) {
    return Integer.valueOf(data1.priority).compareTo(data2.priority);
  }

  @Override
  public boolean equals(Object other) {
    return other == OrderDataByInteger.INSTANCE;
  }

  private Object readResolve() {
    return INSTANCE;
  }
}

このコンパレータはデータを取得しないため、シングルトンにしたことに注意してください。

その後、次のようにキュー ラインを作成できます。

PriorityQueue<Data> queue = new PriorityQueue<Data>(
    initialCapacity, OrderDataByPrority.INSTANCE);

Answer 2

これを行う一般的な方法は次のとおりです。

public class PriorityQueue<T> {

    private java.util.PriorityQueue<IntPriorityComparableWrapper<T>> queue;

    public PriorityQueue() {
            queue = new java.util.PriorityQueue<IntPriorityComparableWrapper<T>>();
    }

    public void add( int priority, T object ) {
            queue.add( new IntPriorityComparableWrapper<T>(object, priority) );
    }

    public T get() {
            return (null != queue.peek())? queue.poll().getObject() : null;
    }


    /**
     * A "wrapper" to impose comparable properties on any object placed in the
     * queue.
     */
    private static class IntPriorityComparableWrapper<T>
    implements Comparable<IntPriorityComparableWrapper<T>> {

            private T object;
            private int priority;

            public IntPriorityComparableWrapper( T object, int priority ) {
                    this.object = object;
                    this.priority = priority;
            }

            public int compareTo( IntPriorityComparableWrapper<T> anotherObject ) {
                    return this.priority - anotherObject.priority;
            }

            public int getPriority() {
                    return priority;
            }

            public T getObject() {
                    return object;
            }
    }

}

Answer 3

これら 2 つのフィールド (と) を含む新しいクラスを作成し、 Comparable (int フィールドでの比較) を実装するのはどうでしょうか。andもオーバーライドすることを忘れないでください(これらのメソッドをオーバーライドする理由については、 Comparable class javadoc を参照してください)。intStringhashCode()equals()

それはあなたが求めているものですか？

Answer 4

複数の要素をキーとして使用する場合は、両方をカプセル化するクラスを作成し、その型をキーとして使用できます。値についても同様です。作成するカスタム キー クラスに対して、このカスタム キー クラスComparable、オーバーライドequals()、およびオーバーライドhashCode()を作成する必要があります。