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

優先度ヒープに基づく、無制限の優先度キューです。このキューは、構築時に指定された順序に従って要素を整列します。この順序は、使用するコンストラクタに応じ、「自然順序付け」(Comparable を参照) または Comparator に従って指定されます。優先度キューでは、null 要素は許可されません。自然順序付けに基づく優先度キューでは、比較不可能なオブジェクトの挿入も許可されません (実行すると ClassCastException がスローされる)。

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

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

このクラスとその反復子は、Collection および Iterator インタフェースの「オプション」メソッドすべてを実装します。iterator() メソッド内で提供される Iterator では、特定の順序で PriorityQueue の要素をたどることは保証されません。要素をたどる順序を指定する必要がある場合は、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 を作成します (Comparable を使用)。

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

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

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

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

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

メソッドの概要

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

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

addAll, element, remove

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

contains, containsAll, isEmpty, removeAll, retainAll, toArray, toArray, toString

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

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

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

contains, containsAll, equals, hashCode, isEmpty, removeAll, retainAll, toArray, toArray

コンストラクタの詳細

PriorityQueue

public PriorityQueue()

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

PriorityQueue

public PriorityQueue(int initialCapacity)

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

パラメータ:

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 を作成します。優先度キューの初期容量は、指定されたコレクションのサイズの 110% です。コレクションが空の場合は、1 になります。指定されたコレクションが SortedSet のインスタンスであるか、別の PriorityQueue である場合、優先度キューは同じコンパレータに従ってソートされますが、コレクションがその要素の自然順序に従ってソートされる場合は、その要素の自然順序に従ってソートされます。それ以外の場合は、優先度キューはその要素の自然順序に従って順序付けされます。

パラメータ:

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

例外:

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

NullPointerException - c またはその内部要素のいずれかが null の場合

PriorityQueue

public PriorityQueue(PriorityQueue<? extends E> c)

指定されたコレクション内の要素を含む PriorityQueue を作成します。優先度キューの初期容量は、指定されたコレクションのサイズの 110% です。コレクションが空の場合は 1 になります。この優先度キューのソートは、指定されたコレクションと同じコンパレータに従って行われますが、コレクションが要素の自然順序に従ってソートされる場合はその要素の自然順序に従います。

パラメータ:

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

例外:

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

NullPointerException - c またはその内部要素のいずれかが null の場合

PriorityQueue

public PriorityQueue(SortedSet<? extends E> c)

指定されたコレクション内の要素を含む PriorityQueue を作成します。優先度キューの初期容量は、指定されたコレクションのサイズの 110% です。コレクションが空の場合は 1 になります。この優先度キューのソートは、指定されたコレクションと同じコンパレータに従って行われますが、コレクションが要素の自然順序に従ってソートされる場合はその要素の自然順序に従います。

パラメータ:

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

例外:

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

NullPointerException - c またはその内部要素のいずれかが null の場合

メソッドの詳細

offer

public boolean offer(E o)

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

定義:

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

パラメータ:

o - 挿入される要素

戻り値:

true

例外:

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

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

peek

public E peek()

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

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

定義:

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

戻り値:

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

add

public boolean add(E o)

指定された要素をこのキューに追加します。

定義:

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

オーバーライド:

クラス AbstractQueue<E> 内の add

パラメータ:

o - 要素

戻り値:

true (Collection.add の一般規約に従う)

例外:

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

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

remove

public boolean remove(Object o)

指定された要素の単一のインスタンスがある場合は、キューから削除します。

定義:

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

オーバーライド:

クラス AbstractCollection<E> 内の remove

パラメータ:

o - コレクションから削除される要素 (その要素がある場合)

戻り値:

コレクションに指定された要素がある場合は true

iterator

public Iterator<E> iterator()

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

定義:

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

定義:

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

定義:

クラス AbstractCollection<E> 内の iterator

戻り値:

キュー内の要素の反復子

size

public int size()

クラス AbstractCollection の記述:

このコレクション中の要素の数を返します。コレクションに 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()

コレクションの順序付けに使うコンパレータを返します。ただし、コレクションがその要素の自然順序付けに従って (Comparable を使用して) ソートされる場合は null を返します。

戻り値:

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