モジュール java.base
パッケージ 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つになります。結付きの解除は任意です。 キューの取得オペレーションpollremovepeek、およびelementは、キューの先頭の要素にアクセスします。

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

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

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

    実装にあたっての注意:この実装は、キューへの登録/登録解除メソッド(offerpollremove()、およびadd)ではO(log(n))時間を、remove(Object)およびcontains(Object)メソッドでは線形時間を、取得メソッド(peekelement、および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)
      指定された要素をこの優先度キューに挿入します。
      boolean remove​(Object o)
      指定された要素の単一のインスタンスがこのキューに存在する場合は、キューから削除します。
      boolean removeAll​(Collection<?> c)
      指定されたコレクションにも格納されているこのコレクションのすべての要素を削除します(オプションの操作)。
      boolean removeIf​(Predicate<? super E> filter)
      指定された述語を満たすこのコレクションの要素をすべて削除します。
      boolean retainAll​(Collection<?> c)
      このコレクションにおいて、指定されたコレクションに格納されている要素だけを保持します(オプションの操作)。
      Spliterator<E> spliterator()
      このキュー内の要素に対する遅延バインディングおよびフェイルファスト Spliteratorを作成します。
      Object[] toArray()
      このキューの要素がすべて含まれている配列を返します。
      <T> T[] toArray​(T[] a)
      このキュー内のすべての要素を含む配列を返します。返される配列の実行時の型は、指定された配列の型です。
      • インタフェース java.util.Queueで宣言されたメソッド

        peek, poll
    • コンストラクタの詳細

      • 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である場合
      • 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>
        戻り値:
        このキュー内の要素のイテレータ
      • clear

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

        public Comparator<? super E> comparator()
        このキュー内の要素を順序付けするために使うコンパレータを返します。ただし、このキューがその要素の自然順序付けに従ってソートされる場合はnullを返します。
        戻り値:
        このキューを順序付けするのに使うコンパレータ。ただし、このキューがその要素の自然順序付けに従ってソートされる場合はnull
      • 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の場合
        関連項目:
        AbstractCollection.remove(Object), AbstractCollection.contains(Object)
      • retainAll

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

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

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

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