優先度付きキューのJava実装

2年 ago

2 minutes

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

優先度付きキューのJava実装

JavaのPriorityQueueのコンストラクターについて言い換えると、

PriorityQueue() – デフォルトの初期容量（11）でPriorityQueueを作成します。
PriorityQueue(Collection c) – 指定されたコレクションの要素を持つPriorityQueueを作成します。
PriorityQueue(int initialCapacity) – 指定された初期容量でPriorityQueueを作成します。
PriorityQueue(int initialCapacity, Comparator comparator) – 指定された初期容量と順序付けに基づく要素のComparatorを持つPriorityQueueを作成します。
PriorityQueue(PriorityQueue c) – 指定されたPriorityQueueに含まれる要素を持つPriorityQueueを作成します。
PriorityQueue(SortedSet c) – 指定されたソートされたセットの要素を持つPriorityQueueを作成します。

優先度キューの要素は、作成時にComparatorが指定されていない限り、自然な順序で並べられます。デフォルトでは昇順で要素が順序づけられるため、キューの最初の要素は優先度が最も低い要素です。もし同時に複数の要素がキューの先頭になる可能性がある場合、そのような場合には任意の方法で選ばれます。

「Javaにおける優先度付きキューの例」

様々なタスクを含む優先度付きキューを作成しましょう。

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 メソッド

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

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

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

出力は以下のようになります：
null
java.util.Collections$ReverseComparator@15db9742

boolean contains(Object o) – キューに指定された要素が含まれている場合はtrueを返します。”task3″が優先順位付きキューtasksに含まれているかどうかを確認してみましょう：

System.out.println(tasks.contains(“task3”));

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

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

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

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

次のような出力が得られます：
task1
task5

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

System.out.println(“tasksでのPoll：” + tasks.poll());
System.out.println(“reverseTasksでのPoll：” + reverseTasks.poll());

そしてpeekを呼び出すと：
System.out.println(“tasksでのPeek：” + tasks.peek());
System.out.println(“reverseTasksでのPeek：” + reverseTasks.peek());

以下のような出力が得られます：
tasksでのPoll：task1
reverseTasksでのPoll：task5
tasksでのPeek：task2
reverseTasksでのPeek：task4

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

boolean remove(Object o) – 指定された要素をキューから削除します。要素が2つある場合でも、1つだけを削除します。

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

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

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

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

これら以外にも、PriorityQueueはCollectionクラスとObjectクラスのメソッドも継承しています。

JavaのPriorityQueueの時間計算量

データの取得メソッドにおいては、時間の複雑度は定数です。

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