162

私は整数のJavaで優先キューを持っています:

 PriorityQueue<Integer> pq= new PriorityQueue<Integer>();

呼び出すpq.poll()と、最小要素が取得されます。

質問: コードを変更して最大要素を取得するにはどうすればよいですか?

4

17 に答える 17

287

次のようにしたらどうですか:

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
queue.offer(1);
queue.offer(2);
queue.offer(3);
//...

Integer val = null;
while( (val = queue.poll()) != null) {
    System.out.println(val);
}

この場合、 は、 内の要素を自然な順序とは逆の順序でソートする をCollections.reverseOrder()提供します。ComparatorPriorityQueue

于 2012-06-12T19:12:39.727 に答える
102

Java 8 以降、ラムダ式を使用できます。

次のコードは、大きい方の 10 を出力します。

// There is overflow problem when using simple lambda as comparator, as pointed out by Фима Гирин.
// PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);

PriorityQueue<Integer> pq =new PriorityQueue<>((x, y) -> Integer.compare(y, x));

pq.add(10);
pq.add(5);
System.out.println(pq.peek());

ラムダ関数は、入力パラメーターとして 2 つの整数を取り、それらを互いに減算し、算術結果を返します。ラムダ関数は、Functional Interface を実装しComparator<T>ます。(これは、匿名クラスまたは個別の実装とは対照的に、その場で使用されます。)

于 2016-07-09T21:10:33.063 に答える
31

要素を逆の順序でランク付けするカスタムComparatorオブジェクトを提供できます。

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(defaultSize, new Comparator<Integer>() {
    public int compare(Integer lhs, Integer rhs) {
        if (lhs < rhs) return +1;
        if (lhs.equals(rhs)) return 0;
        return -1;
    }
});

現在、優先キューはすべての比較を逆にするため、最小要素ではなく最大要素を取得します。

お役に立てれば!

于 2012-06-12T19:08:29.763 に答える
14
PriorityQueue<Integer> pq = new PriorityQueue<Integer> (
  new Comparator<Integer> () {
    public int compare(Integer a, Integer b) {
       return b - a;
    }
  }
);
于 2016-03-11T17:49:18.597 に答える
9

優先キューの要素は、自然な順序付けに従って、またはキューの構築時に提供される Comparator によって順序付けられます。

Comparator は、compare メソッドをオーバーライドする必要があります。

int compare(T o1, T o2)

デフォルトの比較メソッドは、最初の引数が 2 番目の引数より小さい、等しい、または大きいため、負の整数、ゼロ、または正の整数を返します。

Java によって提供されるデフォルトの PriorityQueue は Min-Heap です。最大ヒープが必要な場合は、次のコードです。

public class Sample {
    public static void main(String[] args) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {

            public int compare(Integer lhs, Integer rhs) {
                if(lhs<rhs) return +1;
                if(lhs>rhs) return -1;
                return 0;
            }
        });
        q.add(13);
        q.add(4);q.add(14);q.add(-4);q.add(1);
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }

}

参考:https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator()

于 2016-11-15T05:19:23.677 に答える
7

これを行うには、Comparator インターフェイスを実装するCustomComparatorクラスを作成し、その比較メソッドをオーバーライドします。以下は同じコードです:

import java.util.PriorityQueue;
import java.util.Comparator;
public class Main
{
    public static void main(String[] args) {
        PriorityQueue<Integer> nums = new PriorityQueue<>(new CustomComparator());
        nums.offer(21);
        nums.offer(1);
        nums.offer(8);
        nums.offer(2);
        nums.offer(-4);
        System.out.println(nums.peek());
    }
}
class CustomComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer n1, Integer n2){
        int val = n1.compareTo(n2);
        if(val > 0)
           return -1;
        else if(val < 0)
            return 1;
        else
            return 0;
    }
}
于 2020-08-06T05:12:55.347 に答える
3

使用できますMinMaxPriorityQueue(Guava ライブラリの一部です): here's the documentation . の代わりにpoll()、メソッドを呼び出す必要がありますpollLast()

于 2013-07-24T16:36:25.373 に答える
2

ダブルヒープソート最小最大の両方のコンパレータでモンテカルロシミュレーションを実行したところ、両方とも同じ結果になりました。

これらは私が使用した最大コンパレータです:

(A) コレクション組み込みコンパレータ

 PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(Collections.reverseOrder());

(B) カスタムコンパレータ

PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(new Comparator<Integer>() {
    int compare(Integer lhs, Integer rhs) {
        if (rhs > lhs) return +1;
        if (rhs < lhs) return -1;
        return 0;
    }
});
于 2015-03-04T09:16:06.633 に答える
0

逆符号で要素をプッシュしてみることができます。例: a=2 & b=5 を追加してから、b=5 をポーリングします。

PriorityQueue<Integer>  pq = new PriorityQueue<>();
pq.add(-a);
pq.add(-b);
System.out.print(-pq.poll());

キューの先頭をポーリングしたら、符号を逆にして使用します。これにより、5 (より大きな要素) が出力されます。単純な実装で使用できます。間違いなく信頼できる修正ではありません。お勧めしません。

于 2016-05-18T16:03:40.983 に答える