優先キュー (データ構造) - DS チュートリアル

優先キューは、各要素に何らかの優先順位があることを除いて、通常のキューと同様に動作する抽象データ型です。つまり、最も高い優先順位を持つ要素が優先キューの最初に配置されます。優先キュー内の要素の優先順位によって、要素が優先キューから削除される順序が決まります。

プライオリティキューは比較可能な要素のみをサポートします。つまり、要素は昇順または降順で配置されます。

Javaでcatchブロックを試してください

たとえば、1、3、4、8、14、22 のようないくつかの値が、値の最小値から最大値の順序で優先キューに挿入されているとします。したがって、1 という数字が最も高い優先順位を持ち、22 という数字は最も低い優先順位を持ちます。

プライオリティキューの特徴

プライオリティキューは、次の特性を含むキューの拡張です。

優先キュー内のすべての要素には、関連付けられた優先順位があります。
優先度の高い要素は、優先度の低い要素が削除される前に削除されます。
優先キュー内の 2 つの要素の優先順位が同じ場合、それらは FIFO 原理を使用して配置されます。

例を通してプライオリティキューを理解しましょう。

次の値を含む優先キューがあります。

1、3、4、8、14、22

すべての値は昇順に並べられます。ここで、次の操作を実行した後にプライオリティキューがどのように見えるかを観察します。

ポーリング():この関数は、優先度キューから最も優先度の高い要素を削除します。上記の優先キューでは、「1」要素の優先順位が最も高いため、優先キューから削除されます。追加(2):この関数は、優先キューに「2」要素を挿入します。 2 はすべての数値の中で最小の要素であるため、最高の優先順位が得られます。ポーリング():優先度キューが最も高いため、優先度キューから「2」要素が削除されます。追加(5):5 は 4 より大きく 8 より小さいため、4 の後に 5 要素が挿入され、優先キュー内で 3 番目に高い優先順位が取得されます。

プライオリティキューの種類

プライオリティキューには 2 つのタイプがあります。

優先キューの表現

ここで、一方向リストを通じて優先キューを表す方法を見ていきます。

以下のリストを使用して優先キューを作成します。情報リストにはデータ要素が含まれており、 PRN リストには、情報リスト、および LINK には基本的に次のノードのアドレスが含まれます。

優先キューを段階的に作成してみましょう。

このデバイス上の非表示のアプリ

優先キューの場合、優先順位番号が小さいほど優先順位が高いとみなされます。つまり、 優先順位の数値が小さいほど優先順位が高くなります。

ステップ1： リストでは、優先度の低い番号は 1 で、そのデータ値は 333 であるため、次の図に示すようにリストに挿入されます。

ステップ2： 333 を挿入した後、優先順位番号 2 の方が高い優先順位を持ち、この優先順位に関連付けられたデータ値は 222 と 111 になります。したがって、このデータは FIFO 原理に基づいて挿入されます。したがって、最初に 222 が追加され、次に 111 が追加されます。

ステップ 3: 優先順位 2 の要素を挿入した後、次に高い優先順位番号は 4 で、4 つの優先順位番号に関連付けられたデータ要素は 444、555、777 になります。この場合、要素は FIFO 原理に基づいて挿入されます。したがって、最初に 444 が追加され、次に 555、次に 777 が追加されます。

ステップ 4: 優先度 4 の要素を挿入した後、次に高い優先度番号は 5 であり、優先度 5 に関連付けられた値は 666 であるため、キューの最後に挿入されます。

プライオリティキューの実装

優先キューは、配列、リンクリスト、ヒープデータ構造、二分探索ツリーを含む 4 つの方法で実装できます。ヒープデータ構造は優先キューを実装する最も効率的な方法であるため、このトピックではヒープデータ構造を使用して優先キューを実装します。ここで、まず、他のすべてのデータ構造の中でヒープが最も効率的な方法である理由を理解します。

さまざまな実装を使用した複雑さの分析

実装	追加	取り除く	ピーク
リンクされたリスト	○(1)	の上）	の上）
バイナリヒープ	O(ログン)	O(ログン)	○(1)
二分探索木	O(ログン)	O(ログン)	○(1)

ヒープとは何ですか?

ヒープは、完全なバイナリツリーを形成し、ヒーププロパティを満たすツリーベースのデータ構造です。 A が B の親ノードである場合、ヒープ内のすべてのノード A および B について、A はノード B に関して順序付けされます。これは、親ノードの値が子ノードの値以上になる可能性があること、または親ノードの値が子ノードの値以下になる可能性があることを意味します。したがって、ヒープには 2 つのタイプがあると言えます。

それぞれのヒープにはちょうど 2 つの子ノードがあるため、両方のヒープはバイナリヒープです。

優先キューの操作

優先キューに対して実行できる一般的な操作は、挿入、削除、ピークです。ヒープデータ構造を維持する方法を見てみましょう。

要素を優先キューに挿入する (最大ヒープ)

優先キューに要素を挿入すると、要素は上から下、左から右に見て空のスロットに移動します。

セマンティックエラー

要素が正しい場所にない場合は、親ノードと比較されます。順序が間違っていることが判明した場合、要素は交換されます。このプロセスは、要素が正しい位置に配置されるまで続きます。

優先キューから最小要素を削除する

ご存知のとおり、最大ヒープでは、最大要素はルートノードです。ルートノードを削除すると、空のスロットが作成されます。最後に挿入された要素は、この空のスロットに追加されます。次に、この要素は子ノード、つまり左の子と右の子と比較され、2 つの小さい方と交換されます。ヒーププロパティが復元されるまでツリーを下降し続けます。

プライオリティキューの用途

プライオリティキューの用途は次のとおりです。

これは、ダイクストラの最短経路アルゴリズムで使用されます。
primのアルゴリズムで使用されています
ハフマンコードなどのデータ圧縮技術で使用されます。
ヒープソートで使用されます。
また、優先スケジューリング、負荷分散、割り込み処理などのオペレーティングシステムでも使用されます。

バイナリ最大ヒープを使用して優先キューを作成するプログラム。

 #include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i &gt; 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong>  </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>

TechCodeview

プライオリティキューとは何ですか?