Java 逆引き集 | PriorityQueue（優先度キュー） — ジョブスケジューラ

Java Java
スポンサーリンク

PriorityQueue（優先度キュー） — ジョブスケジューラ

優先度で「先に処理すべきもの」から取り出せるのが PriorityQueue。デフォルトでは最小値が先頭の最小ヒープ構造で、自然順または Comparator に基づいて並びます。null は入れられず、反復順序はソート保証されません。

使いどころと特性

  • ジョブスケジューラ: 締切（deadline）や優先度（priority）の小さいものを先に処理したいときに最適。
  • 順序付け: 自然順序またはコンストラクタで渡した Comparator に基づく。先頭は「最小要素」になる（最大優先にしたいときは Comparator を逆転）。
  • 禁止事項: null 要素は不可。比較不能オブジェクトを混ぜると ClassCastException の可能性。
  • 反復順: iterator/toArray の並びがヒープ順で、完全なソート順は保証されない。
  • 操作の基本: 追加は offer/add、取り出しは poll（空なら null）、先頭参照は peek（空なら null）。

基本コード例（最小値から取り出し）

import java.util.PriorityQueue;

public class PQBasics {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 自然順序（小さいほど優先）

        pq.add(5);
        pq.add(1);
        pq.add(3);

        System.out.println(pq.peek()); // 1（最小が先頭）
        System.out.println(pq.poll()); // 1 を取り出し
        System.out.println(pq.poll()); // 3
        System.out.println(pq.poll()); // 5
        System.out.println(pq.poll()); // null（空）
    }
}
Java
  • ポイント: 先頭は常に最小要素。最大優先にしたい場合は Comparator を逆順にする。

優先度付きジョブの構造化

例: 締切が近いほど優先、同じなら高い priority を先

import java.util.*;

class Job {
    final String id;
    final long deadlineEpochMillis;
    final int priority; // 大きいほど重要

    Job(String id, long deadlineEpochMillis, int priority) {
        this.id = id; this.deadlineEpochMillis = deadlineEpochMillis; this.priority = priority;
    }
    @Override public String toString() {
        return "%s(d=%d,p=%d)".formatted(id, deadlineEpochMillis, priority);
    }
}

public class JobScheduler {
    public static void main(String[] args) {
        Comparator<Job> byUrgency = Comparator
            .comparingLong((Job j) -> j.deadlineEpochMillis) // 期限が早いほど先
            .thenComparing(Comparator.comparingInt((Job j) -> j.priority).reversed()); // 同期限なら優先度高い順

        PriorityQueue<Job> queue = new PriorityQueue<>(byUrgency);

        queue.add(new Job("A", 1000L, 1));
        queue.add(new Job("B", 900L,  3));
        queue.add(new Job("C", 900L,  2));

        while (!queue.isEmpty()) {
            Job next = queue.poll();
            System.out.println("Dispatch: " + next);
        }
    }
}
Java
  • ポイント: コンストラクタに Comparator を渡すと、任意の優先ルールが適用できる。先頭は指定順序の「最小要素」になる。

最大優先（大きい値から取り出し）

PriorityQueue<Integer> maxPq = new PriorityQueue<>(Comparator.reverseOrder());
maxPq.add(10); maxPq.add(3); maxPq.add(7);
System.out.println(maxPq.poll()); // 10（最大が先頭）
Java
  • ポイント: reverseOrder を使うと最大ヒープ的に振る舞う（内部は最小ヒープだが比較を反転）。

イテレーションと出力の注意

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5); pq.add(1); pq.add(3);

System.out.println(pq); // 表示順はヒープ内部表現、完全な昇順とは限らない
for (Integer x : pq) {
    System.out.println(x); // イテレーション順もソート保証なし
}
// 必ずソート順で出したいなら、poll で順に取り出すか、別途並べ替える
Java
  • 注意: iterator/toArray/文字列表現の順序は「ヒープ順」であり、完全ソートを保証しない。順序保証が必要なら poll で逐次取り出すか、別コレクションへコピーしてソートする。

ジョブスケジューラのミニ実装（時間経過で実行）

import java.util.*;

class ScheduledJob {
    final Runnable task;
    final long scheduledAt; // 実行時刻（ミリ秒）
    ScheduledJob(Runnable task, long scheduledAt) { this.task = task; this.scheduledAt = scheduledAt; }
}

public class MiniScheduler {
    private final PriorityQueue<ScheduledJob> pq =
        new PriorityQueue<>(Comparator.comparingLong(j -> j.scheduledAt));

    public void submit(Runnable task, long delayMillis) {
        long t = System.currentTimeMillis() + delayMillis;
        pq.add(new ScheduledJob(task, t));
    }

    public void runLoop() throws InterruptedException {
        while (true) {
            ScheduledJob head = pq.peek();
            if (head == null) { Thread.sleep(10); continue; }

            long now = System.currentTimeMillis();
            long wait = head.scheduledAt - now;
            if (wait > 0) {
                Thread.sleep(Math.min(wait, 50));
                continue;
            }
            pq.poll().task.run(); // 時刻到達 → 実行
        }
    }

    public static void main(String[] args) throws Exception {
        MiniScheduler sch = new MiniScheduler();
        sch.submit(() -> System.out.println("T1"), 300);
        sch.submit(() -> System.out.println("T2"), 100);
        sch.submit(() -> System.out.println("T3"), 200);
        sch.runLoop(); // T2 → T3 → T1 の順に実行
    }
}
Java
  • ポイント: 先頭は最小 scheduledAt（最も早い実行時刻）。peek で確認し、時刻が来たら poll で取り出して実行。優先度キューの「最小要素が先頭」という性質に依拠している。

よくある落とし穴と回避策

  • null を入れる: 例外。必ず非 null 要素のみを扱う。
  • 比較不能の混入: 自然順序を使う場合、互いに比較可能であることが必要（異種型混在は避ける）。Comparator 指定時も比較が全要素で定義されていること。
  • 反復順を誤解: Iterator の順序は完全ソート保証なし。外部公開や表示で順序が重要なら poll で取り出すか別途ソート。
  • スレッド安全性: PriorityQueue はスレッドセーフではない。並行利用するなら外部同期や PriorityBlockingQueue を検討（API性質の理解と用途分割が必要）。

テンプレート集

  • 基本宣言（自然順）
PriorityQueue<T> pq = new PriorityQueue<>();
Java
  • カスタム順序（Comparator 指定）
PriorityQueue<T> pq = new PriorityQueue<>(Comparator.comparing(T::key1)
                                                    .thenComparing(T::key2));
Java
  • 最大優先
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
Java
  • 主要操作
pq.add(x);     // 追加
pq.offer(x);   // 追加（戻り値で成否）
pq.peek();     // 先頭参照（空なら null）
pq.poll();     // 先頭取り出し（空なら null）
Java

例題で練習

  • 例題1（優先度付き印刷キュー）: 締切の早いジョブから印刷、同締切なら重要度高い方を先に。上の JobScheduler の Comparator を流用してシミュレーション。
  • 例題2（最大値抽出の連続処理）: 数列から常に最大を取り出して加工し、再投入するロジックを PriorityQueue＋reverseOrder で実装。
  • 例題3（遅延タスクの実行）: MiniScheduler を拡張し、キャンセル機能や再実行（固定間隔）を追加してみる。

まとめ

  • PriorityQueue は「最小（または比較で定義した最優先）」を先頭に保つヒープ。自然順または Comparator に基づき、先頭操作（peek/poll）が高速に行える。null 禁止・反復順のソート非保証を理解し、ジョブスケジューラや優先度付き処理で活用するとコードが明快になる。
スポンサーリンク
タイトルとURLをコピーしました