Java Academy · レッスン

順序付き処理のための PriorityQueue

自然順序とカスタム Comparator を使って PriorityQueue を操作し、タスクスケジューリングに活用します。

「順序付き処理のための PriorityQueue」はCoddyKit上の無料Java Academyレッスンです。これはレッスン4/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはJava Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Java Academyコースには全4レッスンが含まれています。

PriorityQueue とは

PriorityQueue はデフォルトでは min-heap です。つまり、自然順序で最も小さい要素が常に先頭になります。要素全体が内部でソートされるわけではなく、先頭に最小要素があることだけが保証されます。

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll()); // 10 (min)
System.out.println(pq.poll()); // 20
System.out.println(pq.poll()); // 30

内部ヒープ構造

PriorityQueue は、配列に格納された二分 min-heap を使用します。インデックス i の親は、インデックス 2i+1 および 2i+2 の子以下になります。これにより、offer/poll は O(log n)、peek は O(1) であることが保証されます。

逆順 Comparator による Max-Heap

Max-heap（最大ヒープ、最大要素を先頭にする）を作成するには、Comparator.reverseOrder() を渡します:

PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
maxPQ.offer(10);
maxPQ.offer(50);
maxPQ.offer(30);

System.out.println(maxPQ.poll()); // 50 (max)
System.out.println(maxPQ.poll()); // 30

カスタムオブジェクトでの PriorityQueue

カスタムレコードやクラスの順序付けには、コンパレータを使用します:

record Job(String name, int priority) {}

PriorityQueue<Job> queue = new PriorityQueue<>(
    Comparator.comparingInt(Job::priority) // ascending priority
);
queue.offer(new Job("Backup", 5));
queue.offer(new Job("Alert", 1));
queue.offer(new Job("Report", 3));

System.out.println(queue.poll().name()); // Alert (priority 1)

Peek と Poll の違い

peek() は先頭要素を削除せずに返します。poll() は先頭要素を削除して返します。空のキューでは、どちらも null を返します（element()/remove() は例外をスローします）。

PriorityQueue<String> pq = new PriorityQueue<>();
pq.offer("banana");
pq.offer("apple");

System.out.println(pq.peek()); // apple (not removed)
System.out.println(pq.peek()); // apple (still there)
System.out.println(pq.poll()); // apple (removed)
System.out.println(pq.peek()); // banana

タスクスケジューリングの例

PriorityQueue は、タスクごとに優先度が異なる CPU スケジューリングのシミュレーションに適しています:

record Task(String name, int priority) {}

PriorityQueue<Task> scheduler = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority).reversed() // highest first
);
scheduler.offer(new Task("Low", 1));
scheduler.offer(new Task("Critical", 10));
scheduler.offer(new Task("Normal", 5));

while (!scheduler.isEmpty()) {
    System.out.println("Processing: " + scheduler.poll().name());
}
// Critical, Normal, Low

K 個の最小要素

PriorityQueue は、配列全体をソートせずに K 個の最小要素を見つけるための典型的なツールです:

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int n : nums) pq.offer(n);

for (int i = 0; i < k; i++) {
    System.out.print(pq.poll() + " ");
}
// 1 2 3

Max-Heap による K 個の最大要素

K 個の最大要素を見つけるには、反復処理中にサイズ K の min-heap を維持する方法もあります:

int[] nums = {7, 2, 5, 1, 9, 3, 8};
int k = 3;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int n : nums) {
    minHeap.offer(n);
    if (minHeap.size() > k) minHeap.poll(); // remove smallest
}
// minHeap now contains the 3 largest: [7, 8, 9]
System.out.println(minHeap); // order may vary

Dijkstra アルゴリズムのパターン

Dijkstra の最短経路アルゴリズムでは、未訪問ノードのうち最もコストの低いノードを常に先に展開するために min-heap を使用します:

record Entry(int node, int cost) {}

PriorityQueue<Entry> pq = new PriorityQueue<>(
    Comparator.comparingInt(Entry::cost)
);
pq.offer(new Entry(0, 0)); // start node, cost 0

while (!pq.isEmpty()) {
    Entry curr = pq.poll();
    System.out.println("Visit node " + curr.node() + " cost=" + curr.cost());
    // expand neighbors...
}

反復処理の順序は保証されない

PriorityQueue を反復処理しても、要素が優先度順に返されることはありません。優先度順になるのは poll() の場合だけです。ソートされた出力が必要な場合は、for-each を使わずに繰り返し poll してください。

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.addAll(List.of(5,3,1,4,2));

// WRONG for sorted output:
for (int n : pq) System.out.print(n+" "); // unordered!

// CORRECT:
while (!pq.isEmpty()) System.out.print(pq.poll()+" "); // 1 2 3 4 5

パフォーマンスのまとめ

PriorityQueue の操作の計算量:

offer(e): O(log n)
poll(): O(log n)
peek(): O(1)
contains(e): O(n)
remove(e): O(n)

スレッドセーフではありません。並行アクセスには PriorityBlockingQueue を使用してください。

確認問題

for-each ループで PriorityQueue を反復処理した場合、要素の順序について何が保証されますか?

まとめ: PriorityQueue

要点:

PriorityQueue は min-heap であり、最小要素が最初に poll されます
Max-heap には Comparator.reverseOrder() を使用します
offer/poll は O(log n)、peek は O(1) です
典型的な用途: K 番目に大きい要素・小さい要素、Dijkstra、タスクスケジューリング
for-each では優先度順にならないため、poll() を使用します

よくある質問

「順序付き処理のための PriorityQueue」レッスンは無料ですか？

はい。「順序付き処理のための PriorityQueue」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Java Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Java Academyコースには全4レッスンが含まれています。

「順序付き処理のための PriorityQueue」で何を学びますか？

自然順序とカスタム Comparator を使って PriorityQueue を操作し、タスクスケジューリングに活用します。ブラウザで直接実行するハンズオンコードでJava Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Java Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのJava Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。これはレッスン4/4です。

「順序付き処理のための PriorityQueue」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このJava Academyレッスンでコードを書いて実行できますか？

はい。すべてのJava Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

← Java Academyに戻る