優先度キューJava

チュートリアル
Java

時折、特定の順序でキューのアイテムを処理する必要があります。優先度キューはその役割を果たすデータ構造です。Javaの優先度キューは「通常の」キューとは異なります。先入れ先出しではなく、優先度に従ってアイテムを取得します。

Javaの優先度キュー

java.util.PriorityQueueクラスは、内部的に優先ヒープの実装を使用して、このようなデータ型の実装を提供します。JavaのPriorityQueueは増加しつづけるキューです。Java 1.5で導入され、Java SE 8で拡張されました。PriorityQueueは、以下の「優先ヒープ」データ構造によって内部的に実装されています。以下はPriorityQueueクラスの階層構造です： PriorityQueueクラスのダイアグラム：

JavaのPriorityQueueコンストラクタ

  1. PriorityQueue() – デフォルトの初期容量（11）でPriorityQueueを作成します。
  2. PriorityQueue(Collection c) – 指定されたコレクション内の要素を持つPriorityQueueを作成します。
  3. PriorityQueue(int initialCapacity) – 指定された初期容量でPriorityQueueを作成します。
  4. PriorityQueue(int initialCapacity, Comparator comparator) – 指定された初期容量とその要素の順序付けに基づいてPriorityQueueを作成します。
  5. PriorityQueue(PriorityQueue c) – 指定された優先度付きキューの要素を含むPriorityQueueを作成します。
  6. PriorityQueue(SortedSet c) – 指定されたソートされたセットの要素を含むPriorityQueueを作成します。

Priority Queueの要素は、Comparatorを提供しない場合は自然な順序で並べ替えられます。要素はデフォルトで昇順に並べ替えられるため、キューの先頭は優先度が最も低い要素です。同時にキューの先頭になる可能性のある2つの要素がある場合、このような引き分けは任意に決定されます。

Java PriorityQueueの例

Stringの自然な順序でタスクを含むPriorityQueueを作成しましょう：

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

これにより、タスクのPriorityQueueが作成され、それはStringの自然な順序で順序付けられます。もう一つのPriorityQueueを作成しましょう。これはタスクを自然な順序の逆順で並べ替えます。したがって、Comparatorを渡す必要があります。

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

Java PriorityQueue Methods

では、PriorityQueueで使用可能なすべてのメソッドを見て、それらを使用しましょう：

  1. Boolean add(E e) – このメソッドは指定された要素をキューに挿入します。このメソッドを使用して、既にキューに5つのタスクを追加しました。

  2. Comparator comparator() – このメソッドは、このキュー内の要素を順序付けるために使用されるComparatorを返します。Comparatorが指定されていない場合やキューが要素の自然な順序に従ってソートされている場合はnullを返します。したがって、次のようにします：

    System.out.println(tasks.comparator());
System.out.println(reverseTasks.comparator());

    出力は次のようになります：

    null
java.util.Collections$ReverseComparator@15db9742

  3. boolean contains(Object o) – 指定された要素がキューに含まれている場合はtrueを返します。”task3″がPriorityQueueのタスクに属しているかどうかを確認しましょう：

    System.out.println(tasks.contains("task3"));

    これは以下を出力します：

    true

  4. boolean offer(E e) – add()メソッドと同様に、このメソッドも要素をキューに追加します。offer()メソッドとadd()メソッドは、容量制約のあるキューの場合には実際には少し異なる動作をしますが、PriorityQueueの場合はどちらも同じです。add()とは異なり、offer()は要素をキューに追加できなかった場合でも例外をスローしません。

  5. E peek() – このキューの先頭を取得します。キューが空の場合はnullを返します。つまり、最も優先度の高い要素を返します。したがって、次のコード：

    System.out.println(tasks.peek());
System.out.println(reverseTasks.peek());

    以下を出力します：

    task1
task5

  6. E poll() – このメソッドは、キューの先頭（最も高い優先順位の要素）を取得するか、キューが空の場合はnullを返します。ただし、peek()とは異なり、要素を削除します。したがって、poll()を呼び出すと：

    System.out.println(“タスクのポーリング： ”+tasks.poll());
System.out.println(“リバースタスクのポーリング： ”+reverseTasks.poll());

    そしてpeek：

    System.out.println(“タスクのピーク： ”+tasks.peek());
System.out.println(“リバースタスクのピーク： ”+reverseTasks.peek());

    次の出力が得られます：

    タスクのポーリング： タスク1
リバースタスクのポーリング： タスク5
タスクのピーク： タスク2
リバースタスクのピーク： タスク4

  7. int size() – キュー内の要素数を返します。

  8. boolean remove(Object o) – 指定された要素をキューから削除します（存在する場合）。同じ要素が2つ存在する場合、そのうちの1つのみを削除します。

  9. Object[] toArray() – キュー内のすべての要素を含む配列を返します。

  10. T[] toArray(T[] a) – キュー内のすべての要素を含む配列を返し、返される配列の型は指定された配列の型です。

  11. Iterator iterator() – キューのイテレータを返します。

  12. void clear() – キューからすべての要素を削除します。

これら以外にも、PriorityQueue は Collection および Object クラスからメソッドを継承しています。

Java PriorityQueue Time Complexity

  1. enqueue および dequeue メソッドの時間複雑度は O(log(n)) です。
  2. remove(Object) および contains(Object) メソッドの時間複雑度は線形です。
  3. 取得メソッドの場合、定数時間の時間複雑度を持ちます。

この優先度付きキューの実装はスレッドセーフではありません。したがって、同期されたアクセスが必要な場合は、PriorityBlockingQueue を使用する必要があります。参照: API Doc

Source:
https://www.digitalocean.com/community/tutorials/priority-queue-java