モジュール java.base
パッケージ 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とメソッドspliterator()で提供されるSpliteratorは、特定の順序で優先順位キューの要素をトラバースすることは保証されません。 要素をトラバースする順序を指定する必要がある場合は、Arrays.sort(pq.toArray())の使用を考慮してください。

この実装はsynchronizedされません。 いずれかのスレッドがキューを変更する場合は、複数のスレッドが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(int initialCapacity)
    自然順序付けに従って要素を順序付けする、指定された初期容量を持つPriorityQueueを作成します。
    PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
    指定されたコンパレータに従って要素を順序付けする、指定された初期容量を持つPriorityQueueを作成します。
    PriorityQueue(Collection<? extends E> c)
    指定されたコレクション内の要素を含むPriorityQueueを作成します。
    PriorityQueue(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()
    このキュー内の要素を順序付けするために使うコンパレータを返します。ただし、このキューがその要素の自然順序付けに従ってソートされる場合はnullを返します。
    boolean
    contains(Object o)
    指定された要素がキューに含まれている場合にtrueを返します。
    void
    forEach(Consumer<? super E> action)
    Iterableの各要素に対して指定されたアクションを、すべての要素が処理されるか、アクションが例外をスローするまで実行します。
    Iterator<E>
    iterator()
    このキュー内の要素のイテレータを返します。
    boolean
    offer(E e)
    指定された要素をこの優先度キューに挿入します。
    E
    peek()
    キューの先頭を取得しますが、削除しません。キューが空の場合はnullを返します。
    E
    poll()
    キューの先頭を取得および削除します。キューが空の場合はnullを返します。
    boolean
    remove(Object o)
    指定された要素の単一のインスタンスがこのキューに存在する場合は、キューから削除します。
    boolean
    removeAll(Collection<?> c)
    指定されたコレクションにも格納されているこのコレクションのすべての要素を削除します(オプションの操作)。
    boolean
    removeIf(Predicate<? super E> filter)
    指定された述語を満たすこのコレクションの要素をすべて削除します。
    boolean
    retainAll(Collection<?> c)
    このコレクションにおいて、指定されたコレクションに格納されている要素だけを保持します(オプションの操作)。
    int
    size()
    このコレクション中の要素の数を返します。
    final Spliterator<E>
    spliterator()
    このキュー内の要素に対する遅延バインディングおよびフェイルファスト Spliteratorを作成します。
    Object[]
    toArray()
    このキューの要素がすべて含まれている配列を返します。
    <T> T[]
    toArray(T[] a)
    このキュー内のすべての要素を含む配列を返します。返される配列の実行時の型は、指定された配列の型です。

    クラス java.util.AbstractQueueで宣言されたメソッド

    addAll, element, remove

    クラス java.util.AbstractCollectionで宣言されたメソッド

    containsAll, isEmpty, toString

    クラス java.lang.Objectで宣言されたメソッド

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

    インタフェース java.util.Collectionで宣言されたメソッド

    containsAll, equals, hashCode, isEmpty, parallelStream, stream, toArray

  • コンストラクタの詳細

    • PriorityQueue

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

    • PriorityQueue

      public PriorityQueue(int initialCapacity)
      自然順序付けに従って要素を順序付けする、指定された初期容量を持つPriorityQueueを作成します。
      パラメータ:
      initialCapacity - この優先度キューの初期容量
      例外:
      IllegalArgumentException - initialCapacityが1より小さい場合

    • PriorityQueue

      public PriorityQueue(Comparator<? super E> comparator)
      デフォルトの初期容量を持ち、指定されたコンパレータに従って要素が順序付けられるPriorityQueueを作成します。
      パラメータ:
      comparator - この優先度キューを順序付けするために使用されるコンパレータ。 nullの場合、要素の自然順序付けが使用される。
      導入されたバージョン:
      1.8

    • 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)
      指定された要素をこの優先度キューに挿入します。
      定義:
      add、インタフェース: Collection<E>
      定義:
      add、インタフェース: Queue<E>
      オーバーライド:
      add、クラス: AbstractQueue<E>
      パラメータ:
      e - 追加する要素
      戻り値:
      true (Collection.add(E)で指定されているとおり)
      例外:
      ClassCastException - 指定された要素と、この優先度キュー内に現在存在している要素との比較を、この優先度キューの順序付けに従って行えない場合
      NullPointerException - 指定された要素がnullである場合

    • offer

      public boolean offer(E e)
      指定された要素をこの優先度キューに挿入します。
      定義:
      offer、インタフェース: Queue<E>
      パラメータ:
      e - 追加する要素
      戻り値:
      true (Queue.offer(E)で指定されているとおり)
      例外:
      ClassCastException - 指定された要素と、この優先度キュー内に現在存在している要素との比較を、この優先度キューの順序付けに従って行えない場合
      NullPointerException - 指定された要素がnullである場合

    • peek

      public E peek()
      インタフェースからコピーされた説明: Queue
      キューの先頭を取得しますが、削除しません。キューが空の場合はnullを返します。
      定義:
      peek、インタフェース: Queue<E>
      戻り値:
      キューの先頭。キューが空の場合はnull

    • remove

      public boolean remove(Object o)
      指定された要素の単一のインスタンスがこのキューに存在する場合は、キューから削除します。 つまり、キュー内に、o.equals(e)に該当する要素eが1つ以上含まれている場合は、そのような要素を削除します。 指定された要素がこのキューに含まれていた場合(つまり、呼出しの結果としてこのキューが変更された場合)にのみtrueを返します。
      定義:
      remove、インタフェース: Collection<E>
      オーバーライド:
      remove、クラス: AbstractCollection<E>
      パラメータ:
      o - キューから削除される要素(その要素が存在する場合)
      戻り値:
      この呼出しの結果、このキューが変更された場合はtrue

    • contains

      public boolean contains(Object o)
      指定された要素がキューに含まれている場合にtrueを返します。 つまり、このキュー内にo.equals(e)のような1つ以上の要素eが含まれている場合、trueを返します。
      定義:
      contains、インタフェース: Collection<E>
      オーバーライド:
      contains、クラス: AbstractCollection<E>
      パラメータ:
      o - このキューに含まれているかどうかを調べるオブジェクト
      戻り値:
      指定された要素がこのキューに含まれている場合はtrue

    • toArray

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

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

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

      定義:
      toArray、インタフェース: Collection<E>
      オーバーライド:
      toArray、クラス: AbstractCollection<E>
      戻り値:
      このキューのすべての要素が含まれている配列

    • 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()と同一です。

      定義:
      toArray、インタフェース: Collection<E>
      オーバーライド:
      toArray、クラス: AbstractCollection<E>
      型パラメータ:
      T - コレクションを格納する配列のコンポーネント型
      パラメータ:
      a - 配列が十分な大きさを持つ場合は、キューの要素の格納先の配列。配列のサイズが十分でない場合は、同じ実行時の型で新しい配列が格納用として割り当てられる。
      戻り値:
      このキューのすべての要素が含まれている配列
      例外:
      ArrayStoreException - 指定された配列の実行時の型が、このキュー内の各要素の実行時の型のスーパー・タイプでない場合
      NullPointerException - 指定された配列がnullである場合

    • iterator

      public Iterator<E> iterator()
      このキュー内の要素のイテレータを返します。 イテレータは特定の順序で要素を返しません。
      定義:
      iterator、インタフェース: Collection<E>
      定義:
      iterator、インタフェース: Iterable<E>
      定義:
      iterator、クラス: AbstractCollection<E>
      戻り値:
      このキュー内の要素のイテレータ

    • size

      public int size()
      次のインタフェースからコピーされた説明: Collection
      このコレクション中の要素の数を返します。 このコレクションにInteger.MAX_VALUEより多くの要素がある場合は、Integer.MAX_VALUEを返します。
      定義:
      size、インタフェース: Collection<E>
      戻り値:
      このコレクションの要素数

    • clear

      public void clear()
      すべての要素をこの優先度キューから削除します。 この呼出しが戻ると、キューは空になります。
      定義:
      clear、インタフェース: Collection<E>
      オーバーライド:
      clear、クラス: AbstractQueue<E>

    • poll

      public E poll()
      インタフェースからコピーされた説明: Queue
      キューの先頭を取得および削除します。キューが空の場合はnullを返します。
      定義:
      poll、インタフェース: Queue<E>
      戻り値:
      キューの先頭。キューが空の場合はnull

    • comparator

      public Comparator<? super E> comparator()
      このキュー内の要素を順序付けするために使うコンパレータを返します。ただし、このキューがその要素の自然順序付けに従ってソートされる場合はnullを返します。
      戻り値:
      このキューを順序付けするのに使うコンパレータ。ただし、このキューがその要素の自然順序付けに従ってソートされる場合はnull

    • spliterator

      public final Spliterator<E> spliterator()
      このキュー内の要素に対する遅延バインディングおよびフェイルファスト Spliteratorを作成します。 spliteratorは、特定の順序で要素をトラバースしません(ORDERED特性は報告されません)。

      Spliteratorは、Spliterator.SIZED、Spliterator.SUBSIZEDおよびSpliterator.NONNULLを報告します。 オーバーライドする実装は、追加の特性値の報告をドキュメント化する必要があります。

      定義:
      spliterator、インタフェース: Collection<E>
      定義:
      spliterator、インタフェース: Iterable<E>
      戻り値:
      このキュー内の要素に対するSpliterator
      導入されたバージョン:
      1.8

    • removeIf

      public boolean removeIf(Predicate<? super E> filter)
      次のインタフェースからコピーされた説明: Collection
      指定された述語を満たすこのコレクションの要素をすべて削除します。 反復中に、または述語によってスローされたエラーまたは実行時例外は、呼出し側に中継されます。
      定義:
      removeIf、インタフェース: Collection<E>
      パラメータ:
      filter - 削除される要素に対してtrueを返す述語
      戻り値:
      要素が削除された場合はtrue
      例外:
      NullPointerException - 指定されたフィルタがnullである場合

    • removeAll

      public boolean removeAll(Collection<?> c)
      次のクラスからコピーされた説明: AbstractCollection
      指定されたコレクションにも格納されているこのコレクションのすべての要素を削除します(オプションの操作)。 この呼出しの結果、このコレクションには指定されたコレクションと共通の要素はなくなります。
      定義:
      removeAll、インタフェース: Collection<E>
      オーバーライド:
      removeAll、クラス: AbstractCollection<E>
      パラメータ:
      c - このコレクションから削除される要素を含むコレクション
      戻り値:
      呼出しの結果としてこのコレクションが変更された場合はtrue
      例外:
      NullPointerException - このコレクションに1つ以上のnull要素が含まれており、指定されたコレクションがnull要素をサポートしない場合(オプション)、または指定されたコレクションがnullの場合
      関連項目:

    • retainAll

      public boolean retainAll(Collection<?> c)
      次のクラスからコピーされた説明: AbstractCollection
      このコレクションにおいて、指定されたコレクションに格納されている要素だけを保持します(オプションの操作)。 つまり、指定されたコレクションに格納されていないすべての要素をこのコレクションから削除します。
      定義:
      retainAll、インタフェース: Collection<E>
      オーバーライド:
      retainAll、クラス: AbstractCollection<E>
      パラメータ:
      c - このコレクションで保持される要素を含むコレクション
      戻り値:
      呼出しの結果としてこのコレクションが変更された場合はtrue
      例外:
      NullPointerException - このコレクションに1つ以上のnull要素が含まれており、指定されたコレクションがnull要素を許可しない場合(オプション)、または指定されたコレクションがnullの場合
      関連項目:

    • forEach

      public void forEach(Consumer<? super E> action)
      インタフェースからコピーされた説明: Iterable
      Iterableの各要素に対して指定されたアクションを、すべての要素が処理されるか、アクションが例外をスローするまで実行します。 反復の順序でアクションが実行されます(その順序が指定されている場合)。 アクションによってスローされた例外は、呼出し側に中継されます。

      オーバーライドするクラスが並行変更ポリシーを指定していない限り、アクションが要素の基本ソースを変更する副作用を実行する場合、このメソッドの動作は指定されていません。

      定義:
      forEach、インタフェース: Iterable<E>
      パラメータ:
      action - 各要素に対して実行されるアクション
      例外:
      NullPointerException - 指定されたアクションがnullである場合