priority queue data structure c with illustration
イラスト付きのC ++での優先キューの概要。
優先キューは、前回のチュートリアルで説明したキューの拡張です。
これは、特定の点でキューに似ていますが、次の点で通常のキューとは異なります。
- 優先度キューの各アイテムは、優先度に関連付けられています。
- 優先度が最も高いアイテムが、キューから最初に削除されるアイテムです。
- 複数のアイテムの優先度が同じである場合、キュー内のそれらの順序が考慮されます。
=> 絶対C ++トレーニングシリーズについては、ここをクリックしてください。
優先度キューは、キューの変更バージョンとして視覚化できます。ただし、アイテムをキューから削除する場合は、優先度が最も高いアイテムが最初に取得されます。そのため、優先度に基づいてアイテムを処理する必要がある場合は、キューではなく優先度キューを使用することをお勧めします。
学習内容：
基本操作
優先キューでサポートされている基本的な操作のいくつかについて説明します。
- 挿入（アイテム、優先度）： 指定された優先度でアイテムを優先度キューに挿入します。
- getHighestPriority（）： 優先度が最も高いアイテムを返します。
- deleteHighestPriority（）： 優先度が最も高いアイテムを削除します。
上記の操作とは別に、isEmpty（）、isFull（）、peek（）などの通常のキュー操作を使用することもできます。
図
優先キューの図を見てみましょう。簡単にするために、優先キューの項目としてASCII文字を使用します。 ASCII値が高いほど、優先度が高くなります。
初期状態–優先キュー（PQ）– {} =>空
上の図から、挿入操作は通常のキューに似ていることがわかります。ただし、優先度キューの「deleteHighestPriority」を呼び出すと、優先度が最も高い要素が最初に削除されます。
したがって、この関数を最初に呼び出すと、アイテムOが削除され、2回目は、アイテムMがGおよびAよりも優先度が高いため削除されます。
C ++での優先キューの実装
優先キューは、次を使用して実装できます。
＃1）配列/リンクリスト
配列を使用して優先度付きキューを実装できます。これは、優先度付きキューの最も簡単な実装です。
優先キュー内のアイテムを表すために、次のように構造体を宣言できます。
struct pq_item{ int item; int priority; };各アイテムの優先順位も宣言しています。
優先度付きキューに新しいアイテムを挿入するには、配列の最後にアイテムを挿入するだけです。
getHighestPriority（）を使用してキューから要素を取得するには、配列を最初からトラバースして、優先度が最も高いアイテムを返す必要があります。
同様に、deleteHighestPriority操作を使用してキューからアイテムを削除するには、配列全体をトラバースして、優先度が最も高いアイテムを削除する必要があります。次に、削除されたアイテムの後の他のすべての要素を1つ後ろに移動します。
リンクリストを使用して優先キューを実装することもできます。配列と同様の方法ですべての操作を実行できます。唯一の違いは、deleteHighestPriorityを呼び出した後に要素を移動する必要がないことです。
＃2）ヒープ
ヒープを使用して優先キューを実装するのが最も効率的な方法であり、リンクリストや配列と比較するとパフォーマンスが大幅に向上します。リンクリストと配列とは異なり、ヒープの実装には、優先キューの挿入操作と削除操作にO（logn）時間がかかります。 get操作、getHighestPriorityはO（1）時間かかります。
＃3）C ++の標準テンプレートライブラリ（STL）に組み込まれた優先度キュー
C ++では、コンテナ適応クラスとして優先キューがあり、最上位の要素がキューの最初の要素であり、すべての要素が降順になるように設計されています。
したがって、優先度キューの各アイテムの優先度は固定されています。
STLには、優先キューの実装を含むクラスがあります。
優先キューでサポートされるさまざまな操作は次のとおりです。
- priority_queue :: size（）： キューのサイズを返します。
- priority_queue :: empty（）： キューが空かどうかを確認し、そのステータスを返します。
- priority_queue ：： top（）： 優先度キューの最上位要素への参照を返します。
- priority_queue :: push（）： 優先キューの最後にアイテムを追加します。
- priority_queue :: pop（）： 優先キューから最初の要素を削除します。
- priority_queue ：： swap（）： あるプライオリティキューの内容を同じタイプおよびサイズの別のキューと交換するために使用されます。
- 優先キュー値タイプ： 値型は、優先度付きキュー内に格納されている要素の型を示します。これは、テンプレートパラメータの同義語としても機能します。
- priority_queue ：： emplace（）： キューの先頭にある優先キューコンテナに新しい要素を挿入するために使用されます。
次のプログラムでは、C ++のSTLの優先度キューの機能を確認します。
#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << '
'; } int main () { priority_queue pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << 'Size of the queue(pq.size()): ' << pq.size(); cout << '
Top element of the queue(pq.top()): ' << pq.top(); cout << '
The priority queue pq is : '; displaypq(pq); cout << '
Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; } 出力：
セレンのクロムでxpathを見つける方法
キューのサイズ（pq.size（））：5
キューの最上位要素（pq.top（））：9
優先キューpqは次のとおりです。9753 1
pq.pop（）操作後の優先キュー：7 5 3 1
優先キューのJava実装
Javaの優先キューは、キュー内のすべての要素が、キューに付属のコンパレータを使用した自然順序付けまたはカスタム順序付けに従って順序付けられる特別なキューです。
Javaの優先キューは次のようになります。
Java優先キューでは、最小の要素がキューの先頭にあり、最大の要素がキューの末尾にあるように要素が配置されます。したがって、優先度付きキューから要素を削除すると、削除されるのは常に最小の要素になります。
Javaで優先度付きキューを実装するクラスは「PriorityQueue」であり、Javaのコレクションフレームワークの一部です。 Javaの「キュー」インターフェースを実装します。
以下は、JavaPriorityQueueクラスのクラス階層です。
以下に示すのは、Javaの項目として整数を使用する優先キュー機能の例です。
import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println('
After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println('
After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( '
Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object() arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i 出力：
peek（）:: Head value：1
優先キュー：
1 3 5 7
poll（）関数の後、優先キュー：
3 7 5
Remove（5）関数の後、優先キュー：
3 7
優先キューに3が含まれていますか？：true
配列要素：
値：3
値：7
上記のプログラムでは、JavaのPriorityQueueクラスを使用して、Integerオブジェクトを含むPriorityQueueのオブジェクトを作成します。 「追加」機能を使用して、要素をキューに追加します。次に、poll（）関数が呼び出され、キューの先頭から最小要素である要素が削除されます。
ここでも、パラメータとして指定された要素をキューから削除する「remove（）」関数を呼び出します。また、「Contains（）」関数を使用して、特定の要素がキューに存在するかどうかを確認します。最後に、「toArray（）」関数を使用してキューを配列オブジェクトに変換します。
応用
- オペレーティングシステムの負荷分散と割り込みハンドラー： 負荷分散や割り込み処理などのオペレーティングシステム機能は、優先キューを使用して実装されます。負荷分散アクティビティは、負荷分散を効果的に実行するために、最も優先度の高いリソースをスケジュールします。割り込み処理は、最も優先度の高い割り込みを処理することによって実行されます。この機能は、優先キューを使用して効果的に実装できます。
- ルーティング： ルーティングは、ネットワークリソースをルーティングするために使用される機能であり、最小のターンアラウンドタイムで最大のスループットを実現します。これは、優先キューを使用して実装することもできます。
- 病院の緊急事態： 病院の救急治療室では、患者の状態の重症度に応じて患者が診察を受けます。これは、優先キューを使用してシミュレートできます。
- ダイクストラの最短経路アルゴリズム： ここでは、グラフが隣接リストとして保存され、優先度キューを使用して隣接リストから最小の重み付きエッジを効率的に抽出し、ダイクストラの最短パスアルゴリズムを実装できます。
- 優先キューを使用して、スパニングツリーの実装中にノードキーを格納し、最小キーノードを抽出することもできます。
結論
優先キューは、キューの拡張に他なりません。ただし、FIFOアプローチを使用してアイテムを追加/削除するキューとは異なり、優先キューでは、優先度に従ってアイテムがキューから削除されます。したがって、キュー内の各アイテムは優先度に関連付けられ、優先度が最も高いアイテムが最初にキューから削除されます。
優先度付きキューには、挿入（）、getHighestPriority（）、deleteHighestPriority（）の3つの主要な操作があります。優先キューは、配列またはリンクリストを使用して実装できますが、作業はあまり効率的ではありません。優先キューはヒープを使用して実装することもでき、パフォーマンスははるかに高速です。
C ++には、優先度付きキューの機能を実装するコンテナクラスもあります。 Javaには、優先キューの機能を提供する組み込みクラスpriority_queueがあります。
優先度キューは主に、優先度に従ってアイテムを処理する必要があるアプリケーションで使用されます。 例えば、 割り込み処理で使用されます。
次のチュートリアルでは、キューのさらに別の拡張機能である循環キューについてすべて説明します。
=> 専門家による完全なC ++コースについては、こちらをご覧ください。
推奨読書