導入：なぜ PriorityQueue が重要なのか
通常の Queue（FIFO：先入れ先出し）とは異なり、要素の「優先順位」に基づいて取り出し順が決まるデータ構造が PriorityQueue です。タスクスケジューリングや最短経路探索（ダイクストラ法など）の実装において、要素を逐一ソートするコストをかけずに、「常に最小（または最大）のものを取り出したい」という課題を解決するために非常に重要です。
基礎知識：ヒープ構造とは
PriorityQueue は内部的に「二分ヒープ（Binary Heap）」というデータ構造を利用しています。これは完全二分木の一種で、親ノードが常に子ノードよりも優先度が高い（値が小さい、あるいは大きい）という性質を維持します。
この構造のおかげで、要素の追加や最小値の取り出しが O(log n) という高速な計算量で実行可能です。毎回リストをソートすると O(n log n) かかるため、頻繁に要素を出し入れするシステムでは PriorityQueue を選ぶのが賢明です。
実装・解決策
PriorityQueue を利用する際は、コンストラクタで「何を基準に優先度を決めるか」を指定します。デフォルトでは自然順序（数値なら小さい順）ですが、Comparator を渡すことで柔軟な順序付けが可能です。なお、PriorityQueue はスレッドセーフではないため、マルチスレッド環境では PriorityBlockingQueue を検討してください。
サンプルプログラム
以下のコードは、数値の昇順キューと、カスタムオブジェクトを用いた降順キューの例です。
import java.util.PriorityQueue;
import java.util.Comparator;
public class PriorityQueueExample {
public static void main(String[] args) {
// 1. 基本的な数値の昇順キュー（デフォルト）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(10);
minHeap.add(5);
minHeap.add(20);
// 小さい順に取得される
while (!minHeap.isEmpty()) {
System.out.println("最小値: " + minHeap.poll());
}
// 2. カスタムオブジェクトの降順キュー（Comparatorを使用）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.add(10);
maxHeap.add(5);
maxHeap.add(20);
// 大きい順に取得される
System.out.println("--- 降順 ---");
while (!maxHeap.isEmpty()) {
System.out.println("最大値: " + maxHeap.poll());
}
}
}
応用・注意点
現場で陥りやすい罠として、「イテレータによる走査は順序を保証しない」という点があります。`for (Integer i : queue)` のようにループを回すと、ヒープ構造のメモリ配置順で出力され、優先順位通りには並びません。順序通りに処理したい場合は、必ず poll() を使用してください。
また、PriorityQueue には null を入れることはできません。無理に挿入すると NullPointerException が発生するため、入力値のバリデーションを忘れないようにしましょう。小規模なデータならリストのソートで十分ですが、データ量が増えるほどヒープ構造の恩恵は大きくなります。ぜひ、要件に応じて使い分けてみてください。
コメント