java.util
クラス PriorityQueue<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractQueue<E>
          java.util.PriorityQueue<E>

型パラメータ:

E - コレクション内に存在する要素の型

すべての実装されたインタフェース:

Serializable, Iterable<E>, Collection<E>, Queue<E>

public class PriorityQueue<E>
extends AbstractQueue<E>
implements Serializable

優先度ヒープに基づく、無制限の優先度キューです。優先度キューの要素の順序付けは、自然順序付けに従って行われるか、キュー構築時に提供される Comparator を使って行われます。そのどちらになるかは、使用するコンストラクタによって決まります。優先度キューでは、null 要素は許可されません。自然順序付けに基づく優先度キューでは、比較不可能なオブジェクトの挿入も許可されません (実行すると ClassCastException がスローされる)。

このキューの「先頭」は、指定された順序付けの「最小」要素です。複数の要素が最小の値に結び付けられている場合、先頭はこれらの要素の 1 つになります。 結び付きの解除は任意です。キューの取得オペレーション poll、remove、peek、および element は、キューの先頭の要素にアクセスします。

優先度キューには制限はありませんが、要素をキューに格納するのに使用する配列サイズを制御する内部「容量」は存在します。どのような場合でも、これはキューのサイズと常に同じ大きさです。要素は優先度キューに追加されるため、容量は自動的に大きくなります。拡大ポリシーの詳細は、指定されません。

このクラスとその反復子は、Collection および Iterator インタフェースの「オプション」メソッドすべてを実装します。iterator() メソッド内で提供される Iterator では、特定の順序で優先度キューの要素をトラバースすることは保証されません。要素をトラバースする順序を指定する必要がある場合は、Arrays.sort(pq.toArray()) の使用を考慮してください。

この実装は同期化されません。いずれかのスレッドがキューを変更する場合は、複数のスレッドが PriorityQueue インスタンスに並行してアクセスしてはいけません。代わりに、スレッドセーフな PriorityBlockingQueue クラスを使用してください。

実装にあたっての注意:この実装は、キューへの登録/登録解除メソッド (offer、poll、remove()、および add) では O(log(n)) 時間を、remove(Object) および contains(Object) メソッドでは線形時間を、取得メソッド (peek、element、および size) では一定時間を、それぞれ提供します。

このクラスは、Java Collections Framework のメンバーです。

導入されたバージョン:

1.5

関連項目:

直列化された形式

コンストラクタの概要

PriorityQueue()
自然順序付け に従って要素を順序付けする、デフォルトの初期容量 (11) を持つ PriorityQueue を作成します。

PriorityQueue(Collection<? extends E> c)
指定されたコレクション内の要素を含む PriorityQueue を作成します。

PriorityQueue(int initialCapacity)
自然順序付け に従って要素を順序付けする、指定された初期容量を持つ PriorityQueue を作成します。

PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
指定されたコンパレータに従って要素を順序付けする、指定された初期容量を持つ PriorityQueue を作成します。

PriorityQueue(PriorityQueue<? extends E> c)
指定された優先度キュー内の要素を含む PriorityQueue を作成します。

PriorityQueue(SortedSet<? extends E> c)
指定されたソートセット内の要素を含む PriorityQueue を作成します。

メソッドの概要

boolean	add(E e) 指定された要素をこの優先度キューに挿入します。
void	clear() すべての要素を優先度キューから削除します。
Comparator<? super E>	comparator() このキュー内の要素を順序付けするのに使うコンパレータを返します。
boolean	contains(Object o) このキューに指定された要素が含まれている場合に true を返します。
Iterator<E>	iterator() このキュー内の要素の反復子を返します。
boolean	offer(E e) 指定された要素をこの優先度キューに挿入します。
E	peek() キューの先頭を取得しますが、削除しません。
E	poll() キューの先頭を取得および削除します。
boolean	remove(Object o) 指定された要素の単一のインスタンスがこのキューに存在する場合は、キューから削除します。
int	size() このコレクション中の要素の数を返します。
Object[]	toArray() このキューの要素がすべて含まれている配列を返します。
<T> T[]	toArray(T[] a) このキュー内のすべての要素を含む配列を返します。

クラス java.util.AbstractQueue から継承されたメソッド

addAll, element, remove

クラス java.util.AbstractCollection から継承されたメソッド

containsAll, isEmpty, removeAll, retainAll, toString

クラス java.lang.Object から継承されたメソッド

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

インタフェース java.util.Collection から継承されたメソッド

containsAll, equals, hashCode, isEmpty, removeAll, retainAll

コンストラクタの詳細

PriorityQueue

public PriorityQueue()

自然順序付け に従って要素を順序付けする、デフォルトの初期容量 (11) を持つ PriorityQueue を作成します。

PriorityQueue

public PriorityQueue(int initialCapacity)

自然順序付け に従って要素を順序付けする、指定された初期容量を持つ PriorityQueue を作成します。

パラメータ:

initialCapacity - この優先度キューの初期容量

例外:

IllegalArgumentException - initialCapacity が 1 より小さい場合

PriorityQueue

public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator)

指定されたコンパレータに従って要素を順序付けする、指定された初期容量を持つ PriorityQueue を作成します。

パラメータ:

initialCapacity - この優先度キューの初期容量

comparator - この優先度キューを順序付けするために使用されるコンパレータ。null の場合、要素の自然順序付けが使用される

例外:

IllegalArgumentException - initialCapacity が 1 より小さい場合

PriorityQueue

public PriorityQueue(Collection<? extends E> c)

指定されたコレクション内の要素を含む PriorityQueue を作成します。指定されたコレクションが SortedSet のインスタンスであるか別の PriorityQueue である場合、この優先度キューの順序付けは、それと同じ順序付けに従って行われます。それ以外の場合、この優先度キューの順序付けは、その要素の 自然順序付け に従って行われます。

パラメータ:

c - 要素が優先度キューに配置されるコレクション

例外:

ClassCastException - 指定されたコレクションの要素を優先度キューの順序付けに従って相互比較できない場合

NullPointerException - 指定されたコレクションまたはそのいずれかの要素が null である場合

PriorityQueue

public PriorityQueue(PriorityQueue<? extends E> c)

指定された優先度キュー内の要素を含む PriorityQueue を作成します。この優先度キューの順序付けは、指定された優先度キューと同じ順序付けに従って行われます。

パラメータ:

c - 要素がこの優先度キューに配置される優先度キュー

例外:

ClassCastException - c の要素を c の順序付けに従って相互比較できない場合

NullPointerException - 指定された優先度キューまたはそのいずれかの要素が null である場合

PriorityQueue

public PriorityQueue(SortedSet<? extends E> c)

指定されたソートセット内の要素を含む PriorityQueue を作成します。この優先度キューの順序付けは、指定されたソートセットと同じ順序付けに従って行われます。

パラメータ:

c - 要素が優先度キューに配置されるソートセット

例外:

ClassCastException - 指定されたソートセットの要素をそのソートセットの順序付けに従って相互比較できない場合

NullPointerException - 指定されたソートセットまたは、その要素のいずれかが null の場合

メソッドの詳細

add

public boolean add(E e)

指定された要素をこの優先度キューに挿入します。

定義:

インタフェース Collection<E> 内の add

定義:

インタフェース Queue<E> 内の add

オーバーライド:

クラス AbstractQueue<E> 内の add

パラメータ:

e - 追加する要素

戻り値:

true (Collection.add(E) で指定された場合と同様)

例外:

ClassCastException - 指定された要素と、この優先度キュー内に現在存在している要素との比較を、この優先度キューの順序付けに従って行えない場合

NullPointerException - 指定された要素が null である場合

offer

public boolean offer(E e)

指定された要素をこの優先度キューに挿入します。

定義:

インタフェース Queue<E> 内の offer

パラメータ:

e - 追加する要素

戻り値:

true (Queue.offer(E) で指定されているとおり)

例外:

ClassCastException - 指定された要素と、この優先度キュー内に現在存在している要素との比較を、この優先度キューの順序付けに従って行えない場合

NullPointerException - 指定された要素が null である場合

peek

public E peek()

インタフェース Queue の記述:

キューの先頭を取得しますが、削除しません。キューが空の場合は null を返します。

定義:

インタフェース Queue<E> 内の peek

戻り値:

キューの先頭。キューが空の場合は null

remove

public boolean remove(Object o)

指定された要素の単一のインスタンスがこのキューに存在する場合は、キューから削除します。つまり、o.equals(e) となる要素 e がこのキュー内に 1 つ以上含まれている場合に、その 1 つを削除します。このキューに指定された要素が含まれていた場合 (つまり、呼び出しの結果としてこのキューが変更された場合) にだけ、true を返します。

定義:

インタフェース Collection<E> 内の remove

オーバーライド:

クラス AbstractCollection<E> 内の remove

パラメータ:

o - キューから削除される要素 (その要素が存在する場合)

戻り値:

キューが呼び出しの結果として変更された場合は true

contains

public boolean contains(Object o)

このキューに指定された要素が含まれている場合に true を返します。つまり、キューに o.equals(e) となる要素 e が 1 つ以上含まれている場合にだけ true を返します。

定義:

インタフェース Collection<E> 内の contains

オーバーライド:

クラス AbstractCollection<E> 内の contains

パラメータ:

o - このキューに含まれているかどうかを調べるオブジェクト

戻り値:

このキューに指定された要素が含まれている場合は true

toArray

public Object[] toArray()

このキューの要素がすべて含まれている配列を返します。要素に特定の順序はありません。

返される配列への参照をこのキューが維持しないという点で、この配列は安全です。(つまり、このメソッドは新しい配列を割り当てる)。このため、呼び出し側は、返された配列を自由に変更できます。

メソッドは、配列ベースの API とコレクションベースの API の間の橋渡し役として機能します。

定義:

インタフェース Collection<E> 内の toArray

オーバーライド:

クラス AbstractCollection<E> 内の toArray

戻り値:

キューのすべての要素が格納されている配列

toArray

public <T> T[] toArray(T[] a)

このキュー内のすべての要素を含む配列を返します。返される配列の実行時の型は、指定された配列の型です。返される配列の要素に特定の順序はありません。キューが指定された配列に収まる場合は、その中に返されます。そうでない場合は、指定された配列の実行時の型とキューのサイズを持つ新しい配列が割り当てられます。

指定された配列にキューが収まってもさらにスペースがある場合、つまり配列にキューより多くの要素がある場合は、コレクションの最後の直後にある配列内の要素は null に設定されます。

toArray() メソッドと同じように、このメソッドは、配列ベースの API とコレクションベースの API の間の橋渡し役として機能します。さらに、このメソッドでは、出力配列の実行時の型を正確に制御できるため、環境によっては割り当ての手間を抑えることができます。

x が、文字列だけからなるキューであることがわかっていると仮定します。次のコードを使うと、新しく割り当てられた String の配列にキューをダンプできます。

     String[] y = x.toArray(new String[0]);

toArray(new Object[0]) は、機能の点で toArray() と同一です。

定義:

インタフェース Collection<E> 内の toArray

オーバーライド:

クラス AbstractCollection<E> 内の toArray

パラメータ:

a - 配列が十分な大きさを持つ場合は、キューの要素が格納される配列。そうでない場合は、要素を格納するために同じ実行時の型の新しい配列が割り当てられる

戻り値:

キューのすべての要素が格納されている配列

例外:

ArrayStoreException - 指定された配列の実行時の型が、キュー内の各要素の実行時の型のスーパータイプでない場合

NullPointerException - 指定された配列が null である場合

iterator

public Iterator<E> iterator()

このキュー内の要素の反復子を返します。反復子が要素を返す特定の順序はありません。

定義:

インタフェース Iterable<E> 内の iterator

定義:

インタフェース Collection<E> 内の iterator

定義:

クラス AbstractCollection<E> 内の iterator

戻り値:

キュー内の要素の反復子

size

public int size()

インタフェース Collection の記述:

このコレクション中の要素の数を返します。このコレクションに Integer.MAX_VALUE より多くの要素がある場合は、Integer.MAX_VALUE を返します。

定義:

インタフェース Collection<E> 内の size

定義:

クラス AbstractCollection<E> 内の size

戻り値:

コレクションの要素数

clear

public void clear()

すべての要素を優先度キューから削除します。この呼び出しが戻ると、キューは空になります。

定義:

インタフェース Collection<E> 内の clear

オーバーライド:

クラス AbstractQueue<E> 内の clear

poll

public E poll()

インタフェース Queue の記述:

キューの先頭を取得および削除します。キューが空の場合は null を返します。

定義:

インタフェース Queue<E> 内の poll

戻り値:

キューの先頭。キューが空の場合は null

comparator

public Comparator<? super E> comparator()

このキュー内の要素を順序付けするのに使うコンパレータを返します。ただし、このキューがその要素の 自然順序付け に従ってソートされる場合は null を返します。

戻り値:

このキューを順序付けするのに使うコンパレータ。ただし、このキューがその要素の自然順序付けに従ってソートされる場合は null