java priority queue tutorial implementation examples
このチュートリアルでは、Java優先度キューと、コンパレータ、最小、最大優先度キューなどの関連概念と、その実装について説明します。
優先キューのデータ構造は、FIFOの順序ではなく、キューの作成時に使用される自然な要素またはカスタムコンパレータに従って要素が存在する特別なキューです。
学習内容：
Javaの優先キュー
優先キューでは、キューの前部は自然な順序に従って最小の要素を持ち、後部はキュー内の最大の要素を指します。
番号で構成される優先キューの例を以下に示します。
負荷テストとパフォーマンステストとストレステスト
したがって、要素が上記の優先度キューから削除されると、その要素は最小の要素になります。
同様に、アルファベット順の優先度付きキューの場合、ASCII値が考慮され、キュー要素はASCII値に従って順序付けられます。
以下に、PriorityQueueの主な特徴のいくつかを示します。
- PriorityQueueはバインドされていないキューです。
- PriorityQueueはnull値を許可しません。
- 比較できないオブジェクトの場合、優先キューを作成することはできません。
- PriorityQueueは、AbstractQueue、AbstractCollection、Collection、Objectなどのクラスから継承します。
- キューの先頭または先頭には、自然な順序に従って最小の要素が含まれています。
- 優先キューの実装はスレッドセーフではありません。したがって、同期アクセスが必要な場合は、PriorityBlockingQueueを使用する必要があります。
PriorityQueueクラスはJavaQueue Interfaceを継承し、java.utilパッケージの一部です。
PriorityQueueクラスの一般的な宣言を以下に示します。
public class PriorityQueue extends AbstractQueue implements Serializable次の図は、PriorityQueueクラスのクラス階層を示しています。
優先キューの時間計算量
- 挿入（エンキュー）および削除（デキュー）メソッドの優先キューの時間計算量はO（log（n））です。
- 優先度付きキューには、削除の時間計算量が線形であり、メソッドが含まれています。
- 優先度付きキューの要素を取得するメソッドには、一定の時間計算量があります。
Javaでの優先キューの例
以下のプログラムは、Javaでの単純なPriorityQueueを示しています。 PriorityQueueクラスのオブジェクトを作成し、それに値を追加してから、Iteratorを使用してキューの内容を表示します。
import java.util.*; class Main{ public static void main(String args()){ PriorityQueue cities_queue=new PriorityQueue(); //initialize the PriorityQueue with values cities_queue.add('Sydney'); cities_queue.add('Venice'); cities_queue.add('New York'); cities_queue.add('California'); cities_queue.add('Melbourne'); //print the head of the PriorityQueue System.out.println('PriorityQueue Head:'+cities_queue.element()); //Define the iterator for PriorityQueue and print its elements System.out.println('
PriorityQueue contents:'); Iterator iter=cities_queue.iterator(); while(iter.hasNext()){ System.out.print(iter.next() + ' '); } } } 出力：
Java優先キューAPIメソッド
コンストラクター：
| コンストラクタープロトタイプ | 説明 | |
|---|---|---|
| ピーク | Eピーク（） | 要素を削除せずにキューの先頭を返します。 |
| PriorityQueue（） | 初期容量が1のPriorityQueueオブジェクトを作成するデフォルトのコンストラクター。 | |
| PriorityQueue（コレクションc） | 指定されたコレクションの初期要素を使用してPriorityQueueオブジェクトを作成しますc。 | |
| PriorityQueue（int initialCapacity） | 指定された「initialCapacity」を使用してPriorityQueueオブジェクトを作成します。要素は自然な順序に従って順序付けられます。 | |
| PriorityQueue（int initialCapacity、コンパレータコンパレータ） | 指定された「initialCapacity」を使用してPriorityQueueオブジェクトを作成します。要素は、指定されたコンパレータに従って順序付けられます。 | |
| PriorityQueue（PriorityQueue c） | cで指定された別のPriorityQueueオブジェクトからPriorityQueueオブジェクトを作成します。 | |
| PriorityQueue（SortedSet c） | cで指定されたSortedSetからPriorityQueueオブジェクトを作成します。 |
メソッド
| 方法 | メソッドプロトタイプ | 説明 |
|---|---|---|
| 追加 | boolean add（E e） | 要素eをPriorityQueueに追加します。 |
| 晴れ | void clear（） | すべての要素を削除してPriorityQueueをクリアします。 |
| コンパレータ | Comparatorcomparator（） | キュー内の要素の順序付けに使用されるカスタムコンパレータを返します。 |
| 含まれています | boolean contains（Object o） | PriorityQueueに指定された要素oが含まれているかどうかを確認します。はいの場合はtrueを返します。 |
| イテレータ | Iteratoriterator（） | 指定されたPriorityQueueのイテレータを取得するメソッド。 |
| 提供 | ブールオファー（E e） | 指定された要素eをPriorityQueueに挿入します。 |
| 投票 | E投票（） | キューの先頭を削除して返します。キューが空の場合はnullを返します。 |
| 削除する | boolean remove（Object o） | 指定された要素oのインスタンスがキューに存在する場合、それを削除します。 |
| サイズ | int size（） | このPriorityQueue内の要素のサイズまたは数を返します。 |
| toArray | Object () toArray（） | 指定されたPriorityQueueの配列表現を返します。 |
| toArray | T () toArray（T () a） | 指定された配列aと同じランタイムタイプを持つ、指定された優先度キューの配列表現を返します。 |
Javaでの実装
Javaプログラムを使用して、上記のPriorityQueueのメソッドを示しましょう。
import java.util.*; class Main { public static void main(String args()) { // Creating empty priority queue PriorityQueue numQueue = new PriorityQueue(); // add elements to numQueue using add() numQueue.add('Five'); numQueue.add('One'); numQueue.add('Seven'); numQueue.add('Three'); numQueue.add('Eleven'); numQueue.add('Nine'); // Print the head element using Peek () method System.out.println('Head element using peek method:' + numQueue.peek()); // Printing all elements System.out.println('
The PriorityQueue elements:'); Iterator iter1 = numQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); // remove head with poll () numQueue.poll(); System.out.println('
After removing an element' + 'with poll function:'); Iterator iter2 = numQueue.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); // Remove 'Three' using remove () numQueue.remove('Three'); System.out.println('
Element 'Three' with' + ' remove function:'); Iterator iter3 = numQueue.iterator(); while (iter3.hasNext()) System.out.print(iter3.next() + ' '); // Check if an element is present in PriorityQueue using contains() boolean ret_val = numQueue.contains('Five'); System.out.println('
Priority queue contains 'Five' ' + 'or not?: ' + ret_val); // get array equivalent of PriorityQueue with toArray () Object() numArr = numQueue.toArray(); System.out.println('
Array Contents: '); for (int i = 0; i 出力：
ソフトウェアエンジニアリングインタビューの質問と回答pdf
Java8の優先キュー
Java 8は、PriorityQueueクラスにもう1つのメソッド、つまり「spliterator（）」を追加します。
この方法の詳細を以下に示します。
メソッド名： スプリッター
メソッドのプロトタイプ： パブリックファイナルスプリッタースプリッター（）
メソッドの説明： このメソッドは、PriorityQueue要素上にスプリッターを作成します。このスプリッターは遅延バインディングであり、フェイルファストです。
優先キューコンパレータ
すでに述べたように、PriorityQueue要素は自然に順序付けられます。順序を変更する場合は、コンパレータを指定して、PriorityQueueオブジェクトの作成時に使用する必要があります。次に、PriorityQueueはこのコンパレータを使用して要素を並べ替えます。
以下のJavaプログラムは、要素の順序付けにカスタムコンパレータを使用する方法を示しています。このプログラムでは、「compare」メソッドをオーバーライドする新しいカスタムコンパレータを定義します。比較メソッドは、長さに応じてPriorityQueueの要素を並べ替えるために使用されます。
import java.util.*; public class Main { public static void main(String() args) { // A custom comparator that compares two Strings by their length. Comparator customComparator = new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } }; // Create a Priority Queue with a custom Comparator PriorityQueue colorsPriorityQueue = new PriorityQueue(customComparator); // Add items to a Priority Queue colorsPriorityQueue.add('Red'); colorsPriorityQueue.add('Green'); colorsPriorityQueue.add('Blue'); colorsPriorityQueue.add('Cyan'); colorsPriorityQueue.add('Magenta'); colorsPriorityQueue.add('Yellow'); // Printing all elements System.out.println('
The PriorityQueue elements with custom Comparator:'); Iterator iter1 = colorsPriorityQueue.iterator(); while (iter1.hasNext()) System.out.print(iter1.next() + ' '); } } 出力：
Javaの最小優先度キュー
優先度付きキューの自然な順序は、キューの先頭に最小または最小の要素があるため、順序は昇順です。これは、要素の昇順で「最小優先度キュー」と呼ばれます。
以下のJavaプログラムは、Javaでの最小優先度キューの実装を示しています。
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with default ordering PriorityQueue pq = new PriorityQueue(); //add element to the PriorityQueue pq.add(8); pq.add(6); pq.add(4); pq.add(2); pq.add(12); pq.add(10); //display the min PriorityQueue System.out.println('The min Priority Queue (natural ordering) contents:'); Integer val = null; while( (val = pq.poll()) != null) { System.out.print(val + ' '); } } } 出力：
Javaの最大優先度キュー
最小優先度キューには昇順の要素がありますが、最大優先度キューには降順の要素があります。つまり、最大優先度キューの先頭はキュー内の最大の要素を返します。
以下のJavaプログラムは、Javaの最大優先度キューを示しています。
import java.util.*; class Main{ public static void main(String args()){ //declare a PriorityQueue object with custom comparator to generate max PQ PriorityQueue pq = new PriorityQueue(new Comparator() { public int compare(Integer lhs, Integer rhs) { if (lhs 出力：
上記のプログラムに示されているように、優先キュー内の要素の自然な順序を変更するには、カスタムコンパレータを定義する必要があります。
よくある質問
Q＃1）Javaの優先キューとは何ですか？
回答： キューのすべての要素が自然な順序に従って、またはカスタムコンパレータを使用して順序付けられる特別なキューは、優先キューと呼ばれます。 FIFOの順序には従いません。
Q＃2）Javaで最大優先度キューを設定するにはどうすればよいですか？
回答： カスタムコンパレータを使用してJavaで最大優先度キューを設定し、キューの先頭がキュー内の最大の要素を返すようにすることができます。
Q＃3）優先キューはJavaの複製を許可しますか？
回答： はい。優先キューでは、値の重複が許可されます。
Q＃4）Java Priorityキューは最大ですか最小ですか？
qaマネージャーの面接の質問と回答
回答： デフォルトでは、Javaの優先度キューは最小優先度キューであり、自然な順序になっています。最大にするために、カスタムコンパレータを使用して、キューの先頭がキュー内の最大の要素を返すようにする必要があります。
Q＃5）優先キューはソートされていますか？
回答： デフォルトでは、キューの先頭がソートされ、優先度キューの先頭として最小の要素があります。残りの要素は、必要に応じて注文されます。
結論
これで、Javaの優先度付きキューに関するチュートリアルは完了です。 Priority Queueは、キューインターフェイスを実装し、要素が自然な順序に従って順序付けられる特別なキューです。 FIFOの順序には従いません。優先キューの自然な順序を変更するには、カスタムコンパレータを使用できます。
優先度付きキューは、主にプリンターのスケジューリング、CPUタスクのスケジューリングなどに使用されます。ヒープ（最小または最大）も優先度付きキューを使用して実装されます。
=> EasyJavaトレーニングシリーズをお読みください。
推奨読書
