Java : PriorityQueue (優先度付きキュー) - API使用例
2023年07月21日
PriorityQueue (Java SE 20 & JDK 20) の使用例まとめです。
だいたいのメソッドを網羅済みです。
API仕様のおともにどうぞ。
概要
優先度ヒープに基づく、制限なしの優先度キューです。 優先度キューの要素は、その自然順序付けに従って、またはキュー構築時に提供されるComparatorで順序付けされます(使用されるコンストラクタに依存)。 優先度キューでは、null要素は許可されません。
PriorityQueue クラスは、自然順序 もしくは Comparator によってソートされる Queue の実装です。
ただし、キューの取得操作である poll や remove, peek 以外 … 例えば、iterator や toArray などは、ソートされていることは保証されません。
record Item(String value, int priority) {
@Override
public String toString() {
return "%s(%d)".formatted(value, priority);
}
}
final var comparator = Comparator.comparingInt(Item::priority);
final var queue = new PriorityQueue<Item>(comparator);
System.out.println(queue); // []
System.out.println(queue.offer(new Item("aaa", 1))); // true
System.out.println(queue.offer(new Item("bbb", 2))); // true
System.out.println(queue.offer(new Item("ccc", 3))); // true
System.out.println(queue.offer(new Item("XXX", 100))); // true
System.out.println(queue.offer(new Item("YYY", 99))); // true
System.out.println(queue.offer(new Item("ZZZ", 98))); // true
System.out.println(queue); // [aaa(1), bbb(2), ccc(3), XXX(100), YYY(99), ZZZ(98)]
System.out.println(queue.poll()); // aaa(1)
System.out.println(queue.poll()); // bbb(2)
System.out.println(queue.poll()); // ccc(3)
System.out.println(queue.poll()); // ZZZ(98)
System.out.println(queue.poll()); // YYY(99)
System.out.println(queue.poll()); // XXX(100)
コンストラクタ
PriorityQueue ()
自然順序付けに従って要素を順序付けする、デフォルトの初期容量(11)を持つPriorityQueueを作成します。
final var queue = new PriorityQueue<String>();
System.out.println(queue); // []
System.out.println(queue.offer("aaa")); // true
System.out.println(queue.offer("bbb")); // true
System.out.println(queue.offer("ccc")); // true
System.out.println(queue); // [aaa, bbb, ccc]
PriorityQueue (int initialCapacity)
自然順序付けに従って要素を順序付けする、指定された初期容量を持つPriorityQueueを作成します。
初期容量(initialCapacity) を変えて処理時間を計った例です。
(実行する環境によって変わる可能性があります)
final var queue = new PriorityQueue<Integer>(10000000);
System.out.println(queue); // []
final var startTime = System.nanoTime();
for (int i = 0; i < 4000000; i++) {
queue.add(i);
}
final var endTime = System.nanoTime();
// 0.115743 sec.
System.out.printf("%f sec.%n", (endTime - startTime) / 1000000000.0);
final var queue = new PriorityQueue<Integer>(1);
System.out.println(queue); // []
final var startTime = System.nanoTime();
for (int i = 0; i < 4000000; i++) {
queue.add(i);
}
final var endTime = System.nanoTime();
// 0.188015 sec.
System.out.printf("%f sec.%n", (endTime - startTime) / 1000000000.0);
PriorityQueue (int initialCapacity, Comparator<? super E> comparator)
指定されたコンパレータに従って要素を順序付けする、指定された初期容量を持つPriorityQueueを作成します。
各パラメータについては、下記の使用例をご参照ください。
- initialCapacity パラメータ : PriorityQueue(int initialCapacity)
- comparator パラメータ : PriorityQueue(Comparator<? super E> comparator)
PriorityQueue (Collection<? extends E> c)
指定されたコレクション内の要素を含むPriorityQueueを作成します。
final var c = List.of("a", "b", "c");
final var queue = new PriorityQueue<>(c);
System.out.println(queue); // [a, b, c]
System.out.println(queue.size()); // 3
PriorityQueue (Comparator<? super E> comparator)
デフォルトの初期容量を持ち、指定されたコンパレータに従って要素が順序付けられるPriorityQueueを作成します。
record Item(String value, int priority) {
@Override
public String toString() {
return "%s(%d)".formatted(value, priority);
}
}
final var comparator = Comparator.comparingInt(Item::priority);
final var queue = new PriorityQueue<Item>(comparator);
System.out.println(queue); // []
System.out.println(queue.offer(new Item("aaa", 1))); // true
System.out.println(queue.offer(new Item("bbb", 2))); // true
System.out.println(queue.offer(new Item("ccc", 3))); // true
System.out.println(queue.offer(new Item("XXX", 100))); // true
System.out.println(queue.offer(new Item("YYY", 99))); // true
System.out.println(queue.offer(new Item("ZZZ", 98))); // true
System.out.println(queue); // [aaa(1), bbb(2), ccc(3), XXX(100), YYY(99), ZZZ(98)]
System.out.println(queue.poll()); // aaa(1)
System.out.println(queue.poll()); // bbb(2)
System.out.println(queue.poll()); // ccc(3)
System.out.println(queue.poll()); // ZZZ(98)
System.out.println(queue.poll()); // YYY(99)
System.out.println(queue.poll()); // XXX(100)
PriorityQueue (PriorityQueue<? extends E> c)
指定された優先度キュー内の要素を含むPriorityQueueを作成します。
final var c = new PriorityQueue<String>(Comparator.reverseOrder());
System.out.println(c.offer("aaa")); // true
System.out.println(c.offer("bbb")); // true
System.out.println(c.offer("ccc")); // true
final var queue = new PriorityQueue<>(c);
System.out.println(queue.poll()); // ccc
System.out.println(queue.poll()); // bbb
System.out.println(queue.poll()); // aaa
PriorityQueue (SortedSet<? extends E> c)
指定されたソート・セット内の要素を含むPriorityQueueを作成します。
final var c = new TreeSet<String>(Comparator.reverseOrder());
System.out.println(c.add("aaa")); // true
System.out.println(c.add("bbb")); // true
System.out.println(c.add("ccc")); // true
System.out.println(c); // [ccc, bbb, aaa]
final var queue = new PriorityQueue<>(c);
System.out.println(queue.poll()); // ccc
System.out.println(queue.poll()); // bbb
System.out.println(queue.poll()); // aaa
メソッド
boolean add (E e)
指定された要素をこの優先度キューに挿入します。
final var queue = new PriorityQueue<String>();
System.out.println(queue); // []
System.out.println(queue.add("aaa")); // true
System.out.println(queue); // [aaa]
System.out.println(queue.add("bbb")); // true
System.out.println(queue); // [aaa, bbb]
System.out.println(queue.add("ccc")); // true
System.out.println(queue); // [aaa, bbb, ccc]
void clear ()
すべての要素をこの優先度キューから削除します。
final var queue = new PriorityQueue<String>();
System.out.println(queue); // []
System.out.println(queue.offer("a")); // true
System.out.println(queue); // [a]
System.out.println(queue.offer("b")); // true
System.out.println(queue); // [a, b]
queue.clear();
System.out.println(queue); // []
Comparator<? super E> comparator ()
このキュー内の要素を順序付けするために使うコンパレータを返します。ただし、このキューがその要素の自然順序付けに従ってソートされる場合はnullを返します。
final var queue = new PriorityQueue<String>();
System.out.println(queue); // []
final var comparator = queue.comparator();
System.out.println(comparator); // null
final var queue = new PriorityQueue<String>(Comparator.reverseOrder());
System.out.println(queue); // []
final var comparator = queue.comparator();
System.out.println(Objects.equals(comparator, Comparator.reverseOrder())); // true
final var queue = new PriorityQueue<>(String.CASE_INSENSITIVE_ORDER);
System.out.println(queue); // []
final var comparator = queue.comparator();
System.out.println(Objects.equals(comparator, String.CASE_INSENSITIVE_ORDER)); // true
boolean contains (Object o)
指定された要素がキューに含まれている場合にtrueを返します。
final var queue = new PriorityQueue<String>();
System.out.println(queue.offer("aaa")); // true
System.out.println(queue.offer("bbb")); // true
System.out.println(queue.offer("ccc")); // true
System.out.println(queue); // [aaa, bbb, ccc]
System.out.println(queue.contains("aaa")); // true
System.out.println(queue.contains("bbb")); // true
System.out.println(queue.contains("XXX")); // false
void forEach (Consumer<? super E> action)
Iterableの各要素に対して指定されたアクションを、すべての要素が処理されるか、アクションが例外をスローするまで実行します。
final var queue = new PriorityQueue<String>();
System.out.println(queue.offer("aaa")); // true
System.out.println(queue.offer("bbb")); // true
System.out.println(queue.offer("ccc")); // true
System.out.println(queue); // [aaa, bbb, ccc]
System.out.println("-- forEach --");
queue.forEach(value -> {
System.out.println("value = " + value);
});
// 結果
// ↓
//-- forEach --
//value = aaa
//value = bbb
//value = ccc
Iterator<E> iterator ()
このキュー内の要素のイテレータを返します。
final var queue = new PriorityQueue<String>();
System.out.println(queue.offer("aaa")); // true
System.out.println(queue.offer("bbb")); // true
System.out.println(queue.offer("ccc")); // true
System.out.println(queue); // [aaa, bbb, ccc]
final var iterator = queue.iterator();
System.out.println("-- forEachRemaining --");
iterator.forEachRemaining(value -> {
System.out.println("value = " + value);
});
// 結果
// ↓
//-- forEachRemaining --
//value = aaa
//value = bbb
//value = ccc
boolean offer (E e)
指定された要素をこの優先度キューに挿入します。
final var queue = new PriorityQueue<String>();
System.out.println(queue); // []
System.out.println(queue.offer("aaa")); // true
System.out.println(queue); // [aaa]
System.out.println(queue.offer("bbb")); // true
System.out.println(queue); // [aaa, bbb]
System.out.println(queue.offer("ccc")); // true
System.out.println(queue); // [aaa, bbb, ccc]
E peek ()
キューの先頭を取得しますが、削除しません。キューが空の場合はnullを返します。
final var queue = new PriorityQueue<String>();
System.out.println(queue); // []
System.out.println(queue.offer("aaa")); // true
System.out.println(queue.offer("bbb")); // true
System.out.println(queue.offer("ccc")); // true
System.out.println(queue.peek()); // aaa
System.out.println(queue); // [aaa, bbb, ccc]
System.out.println(queue.poll()); // aaa
System.out.println(queue); // [bbb, ccc]
System.out.println(queue.peek()); // bbb
System.out.println(queue); // [bbb, ccc]
System.out.println(queue.poll()); // bbb
System.out.println(queue); // [ccc]
System.out.println(queue.peek()); // ccc
System.out.println(queue); // [ccc]
System.out.println(queue.poll()); // ccc
System.out.println(queue); // []
System.out.println(queue.peek()); // null
System.out.println(queue); // []
E poll ()
キューの先頭を取得および削除します。キューが空の場合はnullを返します。
final var queue = new PriorityQueue<String>();
System.out.println(queue); // []
System.out.println(queue.offer("aaa")); // true
System.out.println(queue.offer("bbb")); // true
System.out.println(queue.offer("ccc")); // true
System.out.println(queue); // [aaa, bbb, ccc]
System.out.println(queue.poll()); // aaa
System.out.println(queue); // [bbb, ccc]
System.out.println(queue.poll()); // bbb
System.out.println(queue); // [ccc]
System.out.println(queue.poll()); // ccc
System.out.println(queue); // []
System.out.println(queue.poll()); // null
System.out.println(queue); // []
boolean remove (Object o)
指定された要素の単一のインスタンスがこのキューに存在する場合は、キューから削除します。
final var queue = new PriorityQueue<String>();
System.out.println(queue.offer("aaa")); // true
System.out.println(queue.offer("aaa")); // true
System.out.println(queue.offer("bbb")); // true
System.out.println(queue.offer("bbb")); // true
System.out.println(queue.offer("ccc")); // true
System.out.println(queue); // [aaa, aaa, bbb, bbb, ccc]
System.out.println(queue.remove("aaa")); // true
System.out.println(queue); // [aaa, bbb, bbb, ccc]
System.out.println(queue.remove("bbb")); // true
System.out.println(queue); // [aaa, ccc, bbb]
System.out.println(queue.remove("bbb")); // true
System.out.println(queue); // [aaa, ccc]
System.out.println(queue.remove("XXX")); // false
System.out.println(queue); // [aaa, ccc]
boolean removeAll (Collection<?> c)
指定されたコレクションにも格納されているこのコレクションのすべての要素を削除します(オプションの操作)。
final var src = List.of("a", "b", "a", "b", "A", "B");
System.out.println(src); // [a, b, a, b, A, B]
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.removeAll(List.of())); // false
System.out.println(queue); // [A, a, B, b, b, a]
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.removeAll(List.of("a"))); // true
System.out.println(queue); // [A, B, b, b]
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.removeAll(List.of("a", "b"))); // true
System.out.println(queue); // [A, B]
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.removeAll(List.of("b", "a"))); // true
System.out.println(queue); // [A, B]
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.removeAll(List.of("A"))); // true
System.out.println(queue); // [B, a, b, b, a]
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.removeAll(List.of("X", "Y", "Z"))); // false
System.out.println(queue); // [A, a, B, b, b, a]
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.removeAll(List.of("A", "X", "Y", "Z"))); // true
System.out.println(queue); // [B, a, b, b, a]
}
boolean removeIf (Predicate<? super E> filter)
指定された述語を満たすこのコレクションの要素をすべて削除します。
final var queue = new PriorityQueue<String>();
System.out.println(queue.offer("aaa")); // true
System.out.println(queue.offer("BBB")); // true
System.out.println(queue.offer("ccc")); // true
System.out.println(queue.offer("DDD")); // true
System.out.println(queue); // [BBB, DDD, ccc, aaa]
final var ret = queue.removeIf(s -> {
// 大文字であるかチェックします。
return s.equals(s.toUpperCase());
});
System.out.println(ret); // true
System.out.println(queue); // [aaa, ccc]
final var queue = new PriorityQueue<String>();
System.out.println(queue.offer("aaa")); // true
System.out.println(queue.offer("bbb")); // true
System.out.println(queue); // [aaa, bbb]
final var ret = queue.removeIf(s -> s.equals(s.toUpperCase()));
System.out.println(ret); // false
System.out.println(queue); // [aaa, bbb]
boolean retainAll (Collection<?> c)
このコレクションにおいて、指定されたコレクションに格納されている要素だけを保持します(オプションの操作)。
final var src = List.of("a", "b", "a", "b", "A", "B");
System.out.println(src); // [a, b, a, b, A, B]
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.retainAll(List.of())); // true
System.out.println(queue); // []
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.retainAll(List.of("a", "b"))); // true
System.out.println(queue); // [a, a, b, b]
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.retainAll(List.of("b", "a"))); // true
System.out.println(queue); // [a, a, b, b]
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.retainAll(List.of("A"))); // true
System.out.println(queue); // [A]
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.retainAll(List.of("X", "Y", "Z"))); // true
System.out.println(queue); // []
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.retainAll(List.of("A", "X", "Y", "Z"))); // true
System.out.println(queue); // [A]
}
{
final var queue = new PriorityQueue<>(src);
System.out.println(queue); // [A, a, B, b, b, a]
System.out.println(queue.retainAll(List.of("a", "b", "A", "B"))); // false
System.out.println(queue); // [A, a, B, b, b, a]
}
int size ()
このコレクション中の要素の数を返します。
final var queue = new PriorityQueue<String>();
System.out.println(queue); // []
System.out.println(queue.size()); // 0
System.out.println(queue.offer("aaa")); // true
System.out.println(queue); // [aaa]
System.out.println(queue.size()); // 1
System.out.println(queue.offer("bbb")); // true
System.out.println(queue); // [aaa, bbb]
System.out.println(queue.size()); // 2
System.out.println(queue.offer("ccc")); // true
System.out.println(queue); // [aaa, bbb, ccc]
System.out.println(queue.size()); // 3
queue.clear();
System.out.println(queue); // []
System.out.println(queue.size()); // 0
final Spliterator<E> spliterator ()
このキュー内の要素に対する遅延バインディングおよびフェイルファスト Spliteratorを作成します。
final var queue = new PriorityQueue<String>();
System.out.println(queue.offer("aaa")); // true
System.out.println(queue.offer("bbb")); // true
System.out.println(queue.offer("ccc")); // true
System.out.println(queue); // [aaa, bbb, ccc]
final var spliterator = queue.spliterator();
System.out.println("-- forEachRemaining --");
spliterator.forEachRemaining(value -> {
System.out.println("value = " + value);
});
// 結果
// ↓
//-- forEachRemaining --
//value = aaa
//value = bbb
//value = ccc
Object[] toArray ()
このキューの要素がすべて含まれている配列を返します。
final var queue = new PriorityQueue<String>();
System.out.println(queue.offer("a")); // true
System.out.println(queue.offer("b")); // true
System.out.println(queue.offer("c")); // true
System.out.println(queue); // [a, b, c]
final Object[] array = queue.toArray();
System.out.println(Arrays.toString(array)); // [a, b, c]
<T> T[] toArray (T[] a)
このキュー内のすべての要素を含む配列を返します。返される配列の実行時の型は、指定された配列の型です。
final var queue = new PriorityQueue<String>();
System.out.println(queue.offer("a")); // true
System.out.println(queue.offer("b")); // true
System.out.println(queue.offer("c")); // true
System.out.println(queue); // [a, b, c]
final String[] array = queue.toArray(new String[0]);
System.out.println(Arrays.toString(array)); // [a, b, c]
final var queue = new PriorityQueue<String>();
System.out.println(queue.offer("a")); // true
System.out.println(queue.offer("b")); // true
System.out.println(queue.offer("c")); // true
System.out.println(queue); // [a, b, c]
{
final String[] array = new String[3];
System.out.println(Arrays.toString(array)); // [null, null, null]
final var ret = queue.toArray(array);
System.out.println(Arrays.toString(array)); // [a, b, c]
System.out.println(Arrays.toString(ret)); // [a, b, c]
}
{
final String[] array = new String[5];
System.out.println(Arrays.toString(array)); // [null, null, null, null, null]
final var ret = queue.toArray(array);
System.out.println(Arrays.toString(array)); // [a, b, c, null, null]
System.out.println(Arrays.toString(ret)); // [a, b, c, null, null]
}
{
final String[] array = new String[1];
System.out.println(Arrays.toString(array)); // [null]
final var ret = queue.toArray(array);
System.out.println(Arrays.toString(array)); // [null]
System.out.println(Arrays.toString(ret)); // [a, b, c]
}
AbstractQueueで宣言されたメソッド
addAll, element, remove
「Java API 使用例 : AbstractQueue」をご参照ください。
AbstractCollectionで宣言されたメソッド
containsAll, isEmpty, toString
「Java API 使用例 : AbstractCollection」をご参照ください。
Collectionで宣言されたメソッド
containsAll, equals, hashCode, isEmpty, parallelStream, stream, toArray
「Java API 使用例 : Collection」をご参照ください。
関連記事
- List(リスト)の基本
- Map(マップ)の基本
- Set(セット)の基本
- List の初期化方法いろいろ
- Map の初期化方法いろいろ
- Set の初期化方法いろいろ
- 配列 vs. List
- 配列からListへの変換
- List から配列への変換
- API 使用例
- Collection (コレクション)
- Collections (コレクション操作)
- Comparable
- Comparator
- Iterator
- List (リスト)
- Map (マップ)
- Map.Entry (キーと値のペア)
- Queue (キュー)
- AbstractQueue
- ArrayBlockingQueue (ブロッキング・配列キュー)
- ArrayDeque (両端キュー)
- BlockingDeque (ブロッキング・両端キュー)
- BlockingQueue (ブロッキング・キュー)
- ConcurrentLinkedDeque (並列処理用・両端キュー)
- ConcurrentLinkedQueue (並列処理用キュー)
- Deque (両端キュー)
- LinkedBlockingDeque (ブロッキング・リンク両端キュー)
- LinkedBlockingQueue (ブロッキング・リンクキュー)
- LinkedList (二重リンク・リスト)
- PriorityBlockingQueue (ブロッキング・優先度付きキュー)
- RandomAccess
- Set (セット)
- Spliterator