PriorityQueue は、オブジェクトが優先度に基づいて処理される必要がある場合に使用されます。ことが知られています 列 は先入れ先出しアルゴリズムに従いますが、優先度に従ってキューの要素を処理する必要がある場合があります。その場合には、PriorityQueue が機能します。
PriorityQueue は優先度ヒープに基づいています。優先キューの要素は、使用されるコンストラクターに応じて、自然な順序に従って、またはキューの構築時に提供されるコンパレーターによって順序付けされます。
以下の優先キューでは、最大の ASCII 値を持つ要素が最も高い優先順位を持ちます。
宣言：
public class PriorityQueue extends AbstractQueue implements Serializable where E is the type of elements held in this queue>
クラスが実装するのは、 シリアル化可能 、 反復可能 、 コレクション 、 列 インターフェース。
いくつか プライオリティキューの注意点 以下の通り：
- PriorityQueue は null を許可しません。
- 比較できないオブジェクトの PriorityQueue を作成することはできません
- PriorityQueue はバインドされていないキューです。
- このキューの先頭は、指定された順序付けに関して最小の要素です。複数の要素が最小値で結び付けられている場合、先頭はそれらの要素の 1 つになります。結び付けは任意に破られます。
- PriorityQueue はスレッドセーフではないため、Java は Java マルチスレッド環境で使用する BlockingQueue インターフェイスを実装する PriorityBlockingQueue クラスを提供します。
- キューの取得操作では、ポーリング、削除、ピーク、および要素がキューの先頭にある要素にアクセスします。
- これにより、追加メソッドとポーリング メソッドに O(log(n)) 時間がかかります。
- からメソッドを継承します。 抽象キュー 、 抽象コレクション 、 コレクション、 そして 物体 クラス。
コンストラクター:
1.PriorityQueue(): 要素を自然な順序に従って並べ替える、デフォルトの初期容量 (11) で PriorityQueue を作成します。
PriorityQueue pq = 新しい PriorityQueue();
2. PriorityQueue(コレクション c): 指定されたコレクション内の要素を含む PriorityQueue を作成します。
PriorityQueue pq = 新しい PriorityQueue(コレクション c);
3.PriorityQueue(int initialCapacity) : 要素を自然な順序に従って並べ替える、指定された初期容量を持つ PriorityQueue を作成します。
PriorityQueue pq = 新しい PriorityQueue(int initialCapacity);
4. PriorityQueue(int 初期容量、コンパレータ comparator): 指定されたコンパレータに従って要素を順序付けする、指定された初期容量を持つ PriorityQueue を作成します。
PriorityQueue pq = new PriorityQueue(intInitialCapacity, Comparator コンパレータ);
5.PriorityQueue(PriorityQueue c) : 指定された優先キュー内の要素を含む PriorityQueue を作成します。
PriorityQueue pq = 新しい PriorityQueue(PriorityQueue c);
6. PriorityQueue(ソートセットc) : 指定されたソートセット内の要素を含む PriorityQueue を作成します。
PriorityQueue pq = 新しい PriorityQueue(SortedSet c);
7.PriorityQueue(コンパレータコンパレータ): デフォルトの初期容量を使用し、指定されたコンパレータに従って要素が順序付けされた PriorityQueue を作成します。
PriorityQueue pq = 新しい PriorityQueue(コンパレータ c);
例：
以下の例では、プライオリティキューの以下の基本動作を説明します。
CSSセンターボタン
- boolean add(E element): このメソッドは、指定された要素をこの優先キューに挿入します。
- public Peak(): このメソッドは、このキューの先頭を取得しますが、削除はしません。このキューが空の場合は null を返します。
- public poll(): このメソッドは、このキューの先頭を取得して削除します。このキューが空の場合は null を返します。
ジャワ
// Java program to demonstrate the> // working of PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String args[])> >{> >// Creating empty priority queue> >PriorityQueue pQueue =>new> PriorityQueue();> >// Adding items to the pQueue using add()> >pQueue.add(>10>);> >pQueue.add(>20>);> >pQueue.add(>15>);> >// Printing the top element of PriorityQueue> >System.out.println(pQueue.peek());> >// Printing the top element and removing it> >// from the PriorityQueue container> >System.out.println(pQueue.poll());> >// Printing the top element again> >System.out.println(pQueue.peek());> >}> }> |
>
>出力
10 10 15>
PriorityQueue の操作
Priority Queue クラスで頻繁に使用されるいくつかの操作を実行する方法を見てみましょう。
1. 要素の追加: 優先キューに要素を追加するには、add() メソッドを使用できます。広告掲載オーダーは PriorityQueue には保持されません。要素は、デフォルトでは昇順の優先順位に基づいて保存されます。
ジャワ
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >for>(>int> i=>0>;i<>3>;i++){> >pq.add(i);> >pq.add(>1>);> >}> >System.out.println(pq);> >}> }> |
>
>出力
[0, 1, 1, 1, 2, 1]>
PriorityQueue を出力してもソートされた要素は取得されません。
ジャワ
/*package whatever //do not write package name here */> import> java.util.*;> import> java.io.*;> > public> class> PriorityQueueDemo {> > >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> > >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> > >System.out.println(pq);> >}> }> |
>
>出力
[For, Geeks, Geeks]>
2. 要素の削除: 優先キューから要素を削除するには、remove() メソッドを使用できます。このようなオブジェクトが複数ある場合は、最初に出現したオブジェクトが削除されます。それとは別に、poll() メソッドは、ヘッドを削除してそれを返すためにも使用されます。
ジャワ
// Java program to remove elements> // from a PriorityQueue> import> java.util.*;> import> java.io.*;> public> class> PriorityQueueDemo {> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'Initial PriorityQueue '> + pq);> >// using the method> >pq.remove(>'Geeks'>);> >System.out.println(>'After Remove - '> + pq);> >System.out.println(>'Poll Method - '> + pq.poll());> >System.out.println(>'Final PriorityQueue - '> + pq);> >}> }> |
>
>出力
Initial PriorityQueue [For, Geeks, Geeks] After Remove - [For, Geeks] Poll Method - For Final PriorityQueue - [Geeks]>
3. 要素へのアクセス: キューは先入れ先出しの原則に従うため、キューの先頭にしかアクセスできません。優先キューの要素にアクセスするには、peek() メソッドを使用できます。
ジャワ
// Java program to access elements> // from a PriorityQueue> import> java.util.*;> class> PriorityQueueDemo {> > >// Main Method> >public> static> void> main(String[] args)> >{> >// Creating a priority queue> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >System.out.println(>'PriorityQueue: '> + pq);> >// Using the peek() method> >String element = pq.peek();> >System.out.println(>'Accessed Element: '> + element);> >}> }> |
>
>出力
PriorityQueue: [For, Geeks, Geeks] Accessed Element: For>
4. PriorityQueue を反復します。 PriorityQueue を反復処理するには複数の方法があります。最も有名な方法は、キューを配列に変換し、for ループを使用して走査する方法です。ただし、キューには、キューを反復処理するために使用できる組み込みイテレータもあります。
Javaの文字列を置き換える
ジャワ
// Java program to iterate elements> // to a PriorityQueue> import> java.util.*;> public> class> PriorityQueueDemo {> >// Main Method> >public> static> void> main(String args[])> >{> >PriorityQueue pq =>new> PriorityQueue();> >pq.add(>'Geeks'>);> >pq.add(>'For'>);> >pq.add(>'Geeks'>);> >Iterator iterator = pq.iterator();> >while> (iterator.hasNext()) {> >System.out.print(iterator.next() +>' '>);> >}> >}> }> |
>
>出力
For Geeks Geeks>
例：
ジャワ
import> java.util.PriorityQueue;> public> class> PriorityQueueExample {> >public> static> void> main(String[] args) {> > >// Create a priority queue with initial capacity 10> >PriorityQueue pq =>new> PriorityQueue(>10>);> > >// Add elements to the queue> >pq.add(>3>);> >pq.add(>1>);> >pq.add(>2>);> >pq.add(>5>);> >pq.add(>4>);> > >// Print the queue> >System.out.println(>'Priority queue: '> + pq);> > >// Peek at the top element of the queue> >System.out.println(>'Peek: '> + pq.peek());> > >// Remove the top element of the queue> >pq.poll();> > >// Print the queue again> >System.out.println(>'Priority queue after removing top element: '> + pq);> > >// Check if the queue contains a specific element> >System.out.println(>'Does the queue contain 3? '> + pq.contains(>3>));> > >// Get the size of the queue> >System.out.println(>'Size of queue: '> + pq.size());> > >// Remove all elements from the queue> >pq.clear();> > >// Check if the queue is empty> >System.out.println(>'Is the queue empty? '> + pq.isEmpty());> >}> }> |
>
>出力
Priority queue: [1, 3, 2, 5, 4] Peek: 1 Priority queue after removing top element: [2, 3, 4, 5] Does the queue contain 3? true Size of queue: 4 Is the queue empty? true>
リアルタイムの例:
優先キューは、要素が優先順位に従って順序付けされ、最も優先順位の高い要素がキューの先頭に表示されるデータ構造です。以下に、プライオリティ キューが使用できる実際の例をいくつか示します。
- タスクのスケジューリング : オペレーティング システムでは、優先キューを使用して、優先レベルに基づいてタスクをスケジュールします。たとえば、重要なシステム アップデートなどの優先度の高いタスクが、バックグラウンド バックアップ プロセスなどの優先度の低いタスクよりも先にスケジュールされる場合があります。緊急治療室: 病院の緊急治療室では、患者は状態の重症度に基づいてトリアージされ、重篤な状態にある患者が最初に治療されます。優先キューを使用して、医師や看護師が患者を診察する順序を管理できます。ネットワーク ルーティング : コンピュータ ネットワークでは、データ パケットのフローを管理するために優先キューが使用されます。音声データやビデオ データなどの優先度の高いパケットには、電子メールやファイル転送などの優先度の低いデータよりも優先される場合があります。交通 : 交通管理システムでは、優先キューを使用して交通の流れを管理できます。たとえば、救急車などの緊急車両は、目的地に迅速に到着できるように、他の車両よりも優先される場合があります。ジョブ スケジューリング : ジョブ スケジューリング システムでは、優先キューを使用してジョブの実行順序を管理できます。重要なシステム アップデートなどの優先度の高いジョブは、データ バックアップなどの優先度の低いジョブよりも先にスケジュールされる場合があります。オンライン マーケットプレイス : オンライン マーケットプレイスでは、優先キューを使用して顧客への製品の配送を管理できます。速達発送などの優先度の高い注文は、通常の発送注文よりも優先される場合があります。
全体として、優先キューは、現実世界のさまざまなシナリオにおける優先レベルに基づいてタスクとリソースを管理するための便利なデータ構造です。
PriorityQueue クラスのメソッド
| 方法 | 説明 |
|---|---|
| add(そしてそして) | 指定された要素をこの優先キューに挿入します。 |
| クリア（） | この優先キューからすべての要素を削除します。 |
| コンパレータ（） | このキュー内の要素を並べ替えるのに使用されるコンパレータを返します。このキューが要素の自然な順序に従って並べ替えられている場合は null を返します。 |
| を含みますか?(オブジェクト o) | このキューに指定された要素が含まれている場合は true を返します。 |
| forEach?(消費者のアクション) | すべての要素が処理されるか、アクションが例外をスローするまで、Iterable の各要素に対して指定されたアクションを実行します。 |
| イテレータ() | このキュー内の要素に対する反復子を返します。 |
| オファー?(E e) | 指定された要素をこの優先キューに挿入します。 |
| 削除しますか?(オブジェクト o) | 指定された要素の単一インスタンスが存在する場合、このキューから削除します。 |
| すべて削除しますか?(コレクション c) | 指定されたコレクションにも含まれるこのコレクションの要素をすべて削除します (オプションの操作)。 |
| RemoveIf?(述語フィルター) | 指定された述語を満たすこのコレクションの要素をすべて削除します。 |
| すべて保持?(コレクション c) | 指定されたコレクションに含まれるこのコレクション内の要素のみを保持します (オプションの操作)。 |
| スプリッテレータ() | このキュー内の要素に対して遅延バインディングおよびフェイルファストの Spliterator を作成します。 |
| toArray() | このキュー内のすべての要素を含む配列を返します。 |
| toArray?(T[] a) | このキュー内のすべての要素を含む配列を返します。返される配列のランタイム型は、指定された配列のランタイム型です。 |
クラス java.util.AbstractQueue で宣言されたメソッド
| 方法 | 説明 |
|---|---|
| addAll(コレクションc) | 指定されたコレクション内のすべての要素をこのキューに追加します。 |
| 要素（） | このキューの先頭を取得しますが、削除はしません。 |
| 取り除く（） | このキューの先頭を取得して削除します。 |
クラス java.util.AbstractCollection で宣言されたメソッド
| 方法 | 説明 |
|---|---|
| すべてを含む(コレクション c) | このコレクションに指定されたコレクション内のすべての要素が含まれている場合は true を返します。 |
| isEmpty() | このコレクションに要素が含まれていない場合は true を返します。 |
| toString() | このコレクションの文字列表現を返します。 |
インタフェース java.util.Collection で宣言されたメソッド
| 方法 | 説明 |
|---|---|
| すべてを含む(コレクション c) | このコレクションに指定されたコレクション内のすべての要素が含まれている場合は true を返します。 |
| 等しい(オブジェクト o) | 指定されたオブジェクトとこのコレクションが等しいかどうかを比較します。 |
| ハッシュコード（） | このコレクションのハッシュ コード値を返します。 |
| isEmpty() | このコレクションに要素が含まれていない場合は true を返します。 |
| パラレルストリーム() | このコレクションをソースとして持つ、並列可能な Stream を返します。 |
| サイズ（） | このコレクション内の要素の数を返します。 |
| ストリーム（） | このコレクションをソースとして含む連続した Stream を返します。 |
| toArray(IntFunction ジェネレーター) | 提供されたジェネレーター関数を使用して、返された配列を割り当て、このコレクション内のすべての要素を含む配列を返します。 |
インタフェース java.util.Queue で宣言されたメソッド
| 方法 | 説明 |
|---|---|
| ピーク（） | このキューの先頭を取得しますが、削除はしません。このキューが空の場合は null を返します。 |
| ポーリング() | このキューの先頭を取得して削除します。このキューが空の場合は null を返します。 |
アプリケーション :
- ダイクストラとプリムのアルゴリズムを実装します。
- K 回の否定後の配列の合計を最大化する
関連記事 :
- JavaのJava.util.PriorityQueueクラス
- Java のコンパレータを使用して PriorityQueue を実装する