プライオリティキューとは |プライオリティキューの概要 - TECHCODEVIEW.COM

あ 優先キュー 優先順位の値に基づいて要素を配置するキューの一種です。通常、より高い優先順位の値を持つ要素は、より低い優先順位の値を持つ要素よりも前に取得されます。

優先キューでは、各要素に優先順位の値が関連付けられています。要素をキューに追加すると、その要素は優先順位の値に基づいた位置に挿入されます。たとえば、高い優先値を持つ要素を優先キューに追加すると、その要素はキューの先頭近くに挿入され、低い優先値を持つ要素は最後尾近くに挿入されることがあります。

優先キューを実装するには、配列、リンクリスト、ヒープ、または二分探索ツリーの使用など、いくつかの方法があります。各方法には独自の長所と短所があり、最適な選択はアプリケーションの特定のニーズによって異なります。

優先キューは、要素が処理される順序が重大な影響を与える可能性があるリアルタイムシステムでよく使用されます。これらは、効率を向上させるためのアルゴリズムでも使用されます。 ダイクストラのアルゴリズム グラフ内の最短パスを検索するためのアルゴリズムと、パス検索のための A* 検索アルゴリズムを使用します。

プライオリティキューのプロパティ

したがって、プライオリティキューは 列 次のプロパティを備えています。

すべてのアイテムには優先度が関連付けられています。
優先度の高い要素は、優先度の低い要素よりも前にデキューされます。
2 つの要素の優先順位が同じ場合、それらはキュー内の順序に従って処理されます。

以下の優先キューでは、最大の ASCII 値を持つ要素が最も高い優先順位を持ちます。優先度の高い要素が最初に提供されます。

優先度キュー内の要素に優先度はどのように割り当てられますか?

優先キューでは、一般に、要素の値が優先順位の割り当てに考慮されます。

たとえば、最も高い値を持つ要素には最も高い優先順位が割り当てられ、最も低い値を持つ要素には最も低い優先順位が割り当てられます。逆のケースも使用できます。つまり、最も低い値を持つ要素に最も高い優先順位を割り当てることができます。また、ニーズに応じて優先順位を割り当てることもできます。

プライオリティキューの操作:

一般的なプライオリティキューは次の操作をサポートします。

1) プライオリティキューへの挿入

新しい要素が優先キューに挿入されると、空のスロットに上から下、左から右に移動します。ただし、要素が正しい場所にない場合は、親ノードと比較されます。要素の順序が正しくない場合、要素は交換されます。交換プロセスは、すべての要素が正しい位置に配置されるまで続行されます。

2) 優先キュー内の削除

ご存知のとおり、最大ヒープでは、最大要素はルートノードです。そして、優先度が最も高い要素が最初に削除されます。したがって、キューからルートノードを削除します。この削除により空のスロットが作成され、さらに新しい挿入で埋められます。次に、新しく挿入された要素をキュー内のすべての要素と比較して、ヒープの不変性を維持します。

3) 優先キューを覗く

この操作は、優先キューからノードを削除せずに、最大ヒープから最大要素を返すか、最小ヒープから最小要素を返すのに役立ちます。

優先キューの種類:

1) 昇順優先キュー

名前が示すように、昇順優先キューでは、優先順位の値が低い要素に、優先リスト内でより高い優先順位が与えられます。たとえば、優先キューに次の要素が 4、6、8、9、10 のように昇順に配置されているとします。ここで、4 は最小の数値であるため、優先キュー内で最高の優先順位が得られます。そのため、このタイプの優先キューからデキューすると、4 がキューから削除され、デキューは 4 を返します。

2) 降順優先キュー

ご存知のとおり、ルートノードは最大ヒープ内の最大の要素です。また、最も優先度の高い要素が最初に削除されます。その結果、ルートノードがキューから削除されます。この削除により空のスペースが残りますが、このスペースは将来新たに挿入されることで埋められます。ヒープの不変条件は、新しく挿入された要素をキュー内の他のすべてのエントリと比較することによって維持されます。

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

プライオリティキューとノーマルキューの違いは？

キュー内の要素には優先順位が付けられておらず、先入れ先出し (FIFO) の規則が実装されますが、優先キューでは要素に優先順位があります。優先度の高い要素が最初に提供されます。

プライオリティキューを実装するにはどうすればよいですか?

優先キューは、次のデータ構造を使用して実装できます。

配列
リンクされたリスト
ヒープデータ構造
二分探索木

これらすべてについて詳しく説明しましょう。

1) 配列を使用して優先キューを実装します。

簡単な実装は、次の構造の配列を使用することです。

構造体項目 {
整数項目;
整数優先度;
}

enqueue(): この関数は、新しいデータをキューに挿入するために使用されます。 dequeue(): この関数は、最も高い優先順位を持つ要素をキューから削除します。 Peak()/top(): この関数は、キューから削除せずに、キュー内の最も優先度の高い要素を取得するために使用されます。

配列	エンキュー()	それに応じて（）	ピーク（）
時間計算量	○(1)	の上）	の上）

C++

ベースバンドとブロードバンド

Javaのスライス

// C++ program to implement Priority Queue> // using Arrays> #include> using> namespace> std;> // Structure for the elements in the> // priority queue> struct> item {> >int> value;> >int> priority;> };> // Store the element of a priority queue> item pr[100000];> // Pointer to the last index> int> size = -1;> // Function to insert a new element> // into priority queue> void> enqueue(>int> value,>int> priority)> {> >// Increase the size> >size++;> >// Insert the element> >pr[size].value = value;> >pr[size].priority = priority;> }> // Function to check the top element> int> peek()> {> >int> highestPriority = INT_MIN;> >int> ind = -1;> >// Check for the element with> >// highest priority> >for> (>int> i = 0; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >

&& pr[ind].value   highestPriority = pr[i].priority;  ind = i;  }  else if (highestPriority   highestPriority = pr[i].priority;  ind = i;  }  }  // Return position of the element  return ind; } // Function to remove the element with // the highest priority void dequeue() {  // Find the position of the element  // with highest priority  int ind = peek();  // Shift the element one index before  // from the position of the element  // with highest priority is found  for (int i = ind; i   pr[i] = pr[i + 1];  }  // Decrease the size of the  // priority queue by one  size--; } // Driver Code int main() {  // Function Call to insert elements  // as per the priority  enqueue(10, 2);  enqueue(14, 4);  enqueue(16, 4);  enqueue(12, 3);  // Stores the top element  // at the moment  int ind = peek();  cout << pr[ind].value << endl;  // Dequeue the top element  dequeue();  // Check the top element  ind = peek();  cout << pr[ind].value << endl;  // Dequeue the top element  dequeue();  // Check the top element  ind = peek();  cout << pr[ind].value << endl;  return 0; }>

ジャワ

// Java program to implement Priority Queue> // using Arrays> import> java.util.*;> // Structure for the elements in the> // priority queue> class> item {> >public> int> value;> >public> int> priority;> };> class> GFG {> >// Store the element of a priority queue> >static> item[] pr =>new> item[>100000>];> >// Pointer to the last index> >static> int> size = ->1>;> >// Function to insert a new element> >// into priority queue> >static> void> enqueue(>int> value,>int> priority)> >{> >// Increase the size> >size++;> >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> >}> >// Function to check the top element> >static> int> peek()> >{> >int> highestPriority = Integer.MIN_VALUE;> >int> ind = ->1>;> >// Check for the element with> >// highest priority> >for> (>int> i =>0>; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority> >&& ind>->1> >

&& pr[ind].value   highestPriority = pr[i].priority;  ind = i;  }  else if (highestPriority   highestPriority = pr[i].priority;  ind = i;  }  }  // Return position of the element  return ind;  }  // Function to remove the element with  // the highest priority  static void dequeue()  {  // Find the position of the element  // with highest priority  int ind = peek();  // Shift the element one index before  // from the position of the element  // with highest priority is found  for (int i = ind; i   pr[i] = pr[i + 1];  }  // Decrease the size of the  // priority queue by one  size--;  }  public static void main(String[] args)  {  // Function Call to insert elements  // as per the priority  enqueue(10, 2);  enqueue(14, 4);  enqueue(16, 4);  enqueue(12, 3);  // Stores the top element  // at the moment  int ind = peek();  System.out.println(pr[ind].value);  // Dequeue the top element  dequeue();  // Check the top element  ind = peek();  System.out.println(pr[ind].value);  // Dequeue the top element  dequeue();  // Check the top element  ind = peek();  System.out.println(pr[ind].value);  } } // this code is contributed by phasing17>

Python3

import> sys> # Structure for the elements in the> # priority queue> class> item :> >value>=> 0> >priority>=> 0> class> GFG :> > ># Store the element of a priority queue> >pr>=> [>None>]>*> (>100000>)> > ># Pointer to the last index> >size>=> ->1> > ># Function to insert a new element> ># into priority queue> >@staticmethod> >def> enqueue( value, priority) :> > ># Increase the size> >GFG.size>+>=> 1> > ># Insert the element> >GFG.pr[GFG.size]>=> item()> >GFG.pr[GFG.size].value>=> value> >GFG.pr[GFG.size].priority>=> priority> > ># Function to check the top element> >@staticmethod> >def> peek() :> >highestPriority>=> ->sys.maxsize> >ind>=> ->1> > ># Check for the element with> ># highest priority> >i>=> 0> >while> (i <>=> GFG.size) :> > ># If priority is same choose> ># the element with the> ># highest value> >if> (highestPriority>=>=> GFG.pr[i].priority>and> ind>>>->1> and>

GFG.pr[ind].value   highestPriority = GFG.pr[i].priority  ind = i  elif(highestPriority   highestPriority = GFG.pr[i].priority  ind = i  i += 1    # Return position of the element  return ind    # Function to remove the element with  # the highest priority  @staticmethod  def dequeue() :    # Find the position of the element  # with highest priority  ind = GFG.peek()    # Shift the element one index before  # from the position of the element  # with highest priority is found  i = ind  while (i   GFG.pr[i] = GFG.pr[i + 1]  i += 1    # Decrease the size of the  # priority queue by one  GFG.size -= 1  @staticmethod  def main( args) :    # Function Call to insert elements  # as per the priority  GFG.enqueue(10, 2)  GFG.enqueue(14, 4)  GFG.enqueue(16, 4)  GFG.enqueue(12, 3)    # Stores the top element  # at the moment  ind = GFG.peek()  print(GFG.pr[ind].value)    # Dequeue the top element  GFG.dequeue()    # Check the top element  ind = GFG.peek()  print(GFG.pr[ind].value)    # Dequeue the top element  GFG.dequeue()    # Check the top element  ind = GFG.peek()  print(GFG.pr[ind].value)   if __name__=='__main__':  GFG.main([])    # This code is contributed by aadityaburujwale.>

C#

// C# program to implement Priority Queue> // using Arrays> using> System;> // Structure for the elements in the> // priority queue> public> class> item {> >public> int> value;> >public> int> priority;> };> public> class> GFG> {> > >// Store the element of a priority queue> >static> item[] pr =>new> item[100000];> >// Pointer to the last index> >static> int> size = -1;> >// Function to insert a new element> >// into priority queue> >static> void> enqueue(>int> value,>int> priority)> >{> >// Increase the size> >size++;> > >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> >}> > >// Function to check the top element> >static> int> peek()> >{> >int> highestPriority =>int>.MinValue;> >int> ind = -1;> > >// Check for the element with> >// highest priority> >for> (>int> i = 0; i <= size; i++) {> > >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >

&& pr[ind].value   highestPriority = pr[i].priority;  ind = i;  }  else if (highestPriority   highestPriority = pr[i].priority;  ind = i;  }  }    // Return position of the element  return ind;  }    // Function to remove the element with  // the highest priority  static void dequeue()  {  // Find the position of the element  // with highest priority  int ind = peek();    // Shift the element one index before  // from the position of the element  // with highest priority is found  for (int i = ind; i   pr[i] = pr[i + 1];  }    // Decrease the size of the  // priority queue by one  size--;  }  public static void Main(string[] args)  {  // Function Call to insert elements  // as per the priority  enqueue(10, 2);  enqueue(14, 4);  enqueue(16, 4);  enqueue(12, 3);    // Stores the top element  // at the moment  int ind = peek();    Console.WriteLine(pr[ind].value);    // Dequeue the top element  dequeue();    // Check the top element  ind = peek();  Console.WriteLine(pr[ind].value);    // Dequeue the top element  dequeue();    // Check the top element  ind = peek();  Console.WriteLine(pr[ind].value);  } } //this code is contributed by phasing17>

JavaScript

// JavaScript program to implement Priority Queue> // using Arrays> // Structure for the elements in the> // priority queue> class item {> >constructor()> >{> >this>.value;> >this>.priority;> >}> };> // Store the element of a priority queue> let pr = [];> for> (>var> i = 0; i <100000; i++)> >pr.push(>new> item());> // Pointer to the last index> let size = -1;> // Function to insert a new element> // into priority queue> function> enqueue(value, priority)> {> >// Increase the size> >size++;> >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> }> // Function to check the top element> function> peek()> {> >let highestPriority = Number.MIN_SAFE_INTEGER;> >let ind = -1;> >// Check for the element with> >// highest priority> >for> (>var> i = 0; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >

&& pr[ind].value   highestPriority = pr[i].priority;  ind = i;  }  else if (highestPriority   highestPriority = pr[i].priority;  ind = i;  }  }  // Return position of the element  return ind; } // Function to remove the element with // the highest priority function dequeue() {  // Find the position of the element  // with highest priority  let ind = peek();  // Shift the element one index before  // from the position of the element  // with highest priority is found  for (var i = ind; i   pr[i] = pr[i + 1];  }  // Decrease the size of the  // priority queue by one  size--; } // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment let ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // this code is contributed by phasing17>

c 配列内の文字列

出力

16 14 12>

注記： 読む この記事 詳細については。

2) リンクリストを使用して優先キューを実装します。

LinkedList の実装では、エントリは優先順位に基づいて降順に並べ替えられます。最も高い優先度の要素は常に、リンクリストを使用して形成される優先度キューの先頭に追加されます。のような機能 押す（） 、 ポップ（） 、そして ピーク（） リンクリストを使用してプライオリティキューを実装するために使用され、次のように説明されます。

Push(): この関数は、新しいデータをキューに挿入するために使用されます。 Pop(): この関数は、キューから最も高い優先順位を持つ要素を削除します。 Peak() / top(): この関数は、キューから削除せずに、キュー内の最も優先度の高い要素を取得するために使用されます。

リンクされたリスト	押す（）	ポップ（）	ピーク（）
時間計算量	の上）	○(1)	○(1)

C++

// C++ code to implement Priority Queue> // using Linked List> #include> using> namespace> std;> // Node> typedef> struct> node {> >int> data;> >// Lower values indicate> >// higher priority> >int> priority;> >struct> node* next;> } Node;> // Function to create a new node> Node* newNode(>int> d,>int> p)> {> >Node* temp = (Node*)>malloc>(>sizeof>(Node));> >temp->データ = d;>>' temp->優先度 = p;>>' temp->次 = NULL;>>' return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->データ; }>> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->次へ;>> free>(temp);> }> // Function to push according to priority> void> push(Node** head,>int> d,>int> p)> {> >Node* start = (*head);> >// Create new Node> >Node* temp = newNode(d, p);> >// Special Case: The head of list has> >// lesser priority than new node> >if>

((*head)->priority // head の前に新しいノードを挿入 temp->next = *head;  (*頭) = 温度;  } else { // リストを走査し、 // 新しいノードを挿入する位置を見つけます while (start->next != NULL && start->next->priority> p) { start = start->next;  } // リストの最後 // または必要な位置 temp->next = start->next;  開始->次 = 一時;  } } // リストが空かどうかをチェックする関数 int isEmpty(Node** head) { return (*head) == NULL; } // ドライバー コード int main() { // 優先キューを作成します // 7->4->5->6 ノード* pq = newNode(4, 1);  プッシュ(&pq, 5, 2);  プッシュ(&pq, 6, 3);  プッシュ(&pq, 7, 0);  while (!isEmpty(&pq)) { cout<< ' ' << peek(&pq);  pop(&pq);  }  return 0; }>

ジャワ

// Java code to implement Priority Queue> // using Linked List> import> java.util.* ;> class> Solution> {> // Node> static> class> Node {> >int> data;> > >// Lower values indicate higher priority> >int> priority;> >Node next;> > }> static> Node node =>new> Node();> > // Function to Create A New Node> static> Node newNode(>int> d,>int> p)> {> >Node temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> > >return> temp;> }> > // Return the value at head> static> int> peek(Node head)> {> >return> (head).data;> }> > // Removes the element with the> // highest priority from the list> static> Node pop(Node head)> {> >Node temp = head;> >(head) = (head).next;> >return> head;> }> > // Function to push according to priority> static> Node push(Node head,>int> d,>int> p)> {> >Node start = (head);> > >// Create new Node> >Node temp = newNode(d, p);> > >// Special Case: The head of list has lesser> >// priority than new node. So insert new> >// node before head node and change head node.> >if>

((head).priority     // Insert New Node before head  temp.next = head;  (head) = temp;  }  else {    // Traverse the list and find a  // position to insert new node  while (start.next != null &&  start.next.priority>p) { スタート = スタート.ネクスト;  } // リストの最後 // または必要な位置 temp.next = start.next;  開始.次 = 一時;  先頭を返します。 } // リストが空かどうかをチェックする関数 static int isEmpty(Node head) { return ((head) == null)?1:0; } // ドライバーコード public static void main(String args[]) { // 優先キューを作成 // 7.4.5.6 ノード pq = newNode(4, 1);  pq =push(pq, 5, 2);  pq =push(pq, 6, 3);  pq =push(pq, 7, 0);    while (isEmpty(pq)==0) { System.out.printf('%d ', Peak(pq));  pq=ポップ(pq);  } } } // このコードは ishankhandelwals によって寄稿されました。>>

データ構造を試す

パイソン

# Python3 code to implement Priority Queue> # using Singly Linked List> # Class to create new node which includes> # Node Data, and Node Priority> class> PriorityQueueNode:> >def> _init_(>self>, value, pr):> >self>.data>=> value> >self>.priority>=> pr> >self>.>next> => None> # Implementation of Priority Queue> class> PriorityQueue:> >def> _init_(>self>):> >self>.front>=> None> ># Method to check Priority Queue is Empty> ># or not if Empty then it will return True> ># Otherwise False> >def> isEmpty(>self>):> >return> True> if> self>.front>=>=> None> else> False> ># Method to add items in Priority Queue> ># According to their priority value> >def> push(>self>, value, priority):> ># Condition check for checking Priority> ># Queue is empty or not> >if> self>.isEmpty()>=>=> True>:> ># Creating a new node and assigning> ># it to class variable> >self>.front>=> PriorityQueueNode(value,> >priority)> ># Returning 1 for successful execution> >return> 1> >else>:> ># Special condition check to see that> ># first node priority value> >if> self>

.front.priority   # Creating a new node  newNode = PriorityQueueNode(value,  priority)  # Updating the new node next value  newNode.next = self.front  # Assigning it to self.front  self.front = newNode  # Returning 1 for successful execution  return 1  else:  # Traversing through Queue until it  # finds the next smaller priority node  temp = self.front  while temp.next:  # If same priority node found then current  # node will come after previous node  if priority>= temp.next.priority: Break temp = temp.next newNode = PriorityQueueNode(value, priority) newNode.next = temp.next temp.next = newNode # 実行が成功した場合は 1 を返す return 1 # 優先度の高い項目 # を削除するメソッド優先キュー def Pop(self): # 優先キューが空かどうかを確認するための条件チェック if self.isEmpty() == True: return else: # 優先キューから高優先ノードを削除し、 # 先頭を次のノードで更新node self.front = self.front.next return 1 # 優先度の高いノードを返すメソッド # 値を削除しない def Peak(self): # 優先度をチェックするための条件チェック # キューが空かどうか if self.isEmpty() == True: return else: return self.front.data # 優先度をトラバースするメソッド # キュー def traverse(self): # 優先度をチェックするための条件チェック # キューが空かどうか if self.isEmpty() == True: return 'キューは空です!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # ドライバー コード if _name_ == '_main_': # ドライバー コードPriority # Queue のインスタンスと値の加算 # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # 優先キューを通過する pq.traverse() # 優先キューの最高優先項目を削除 # pq.pop()>>

C#

// C# code to implement Priority Queue> // using Linked List> using> System;> class> GFG> {> >// Node> >public> class> Node> >{> >public> int> data;> >// Lower values indicate> >// higher priority> >public> int> priority;> >public> Node next;> >}> >public> static> Node node =>new> Node();> >// Function to Create A New Node> >public> static> Node newNode(>int> d,>int> p)> >{> >Node temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> >}> >// Return the value at head> >public> static> int> peek(Node head)> >{> >return> (head).data;> >}> >// Removes the element with the> >// highest priority from the list> >public> static> Node pop(Node head)> >{> >Node temp = head;> >(head) = (head).next;> >return> head;> >}> >// Function to push according to priority> >public> static> Node push(Node head,> >int> d,>int> p)> >{> >Node start = (head);> >// Create new Node> >Node temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if>

((head).priority   {   // Insert New Node before head   temp.next = head;   (head) = temp;   }   else  {   // Traverse the list and find a   // position to insert new node   while (start.next != null &&   start.next.priority>p) { スタート = スタート.ネクスト;   } // リストの最後 // または必要な位置 temp.next = start.next;   開始.次 = 一時;   先頭を返します。   } // リストが空かどうかをチェックする関数 public static int isEmpty(Node head) { return ((head) == null) ? 1:0;   } // ドライバーコード public static void Main(string[] args) { // 優先キューを作成します // 7.4.5.6 ノード pq = newNode(4, 1);   pq = プッシュ(pq, 5, 2);   pq = プッシュ(pq, 6, 3);   pq = プッシュ(pq, 7, 0);   while (isEmpty(pq) == 0) { Console.Write('{0:D} ', Peak(pq));   pq = ポップ(pq);   } } } // このコードは ishankhandelwals によって提供されました。>>

JavaScript

// JavaScript code to implement Priority Queue> // using Linked List> // Node> class Node {> >// Lower values indicate> >// higher priority> >constructor() {> >this>.data = 0;> >this>.priority = 0;> >this>.next =>null>;> >}> }> var> node =>new> Node();> // Function to Create A New Node> function> newNode(d, p) {> >var> temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> }> // Return the value at head> function> peek(head) {> >return> head.data;> }> // Removes the element with the> // highest priority from the list> function> pop(head) {> >var> temp = head;> >head = head.next;> >return> head;> }> // Function to push according to priority> function> push(head, d, p) {> >var> start = head;> >// Create new Node> >var> temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if>

(head.priority   // Insert New Node before head  temp.next = head;  head = temp;  }  else {  // Traverse the list and find a  // position to insert new node  while (start.next != null && start.next.priority>p) { スタート = スタート.ネクスト;  } // リストの最後 // または必要な位置 temp.next = start.next;  開始.次 = 一時;  先頭を返します。 } // リストが空かどうかをチェックする関数 function isEmpty(head) { return head == null ? 1:0; } // ドライバー コード // 優先キューを作成します // 7.4.5.6 var pq = newNode(4, 1); pq = プッシュ(pq, 5, 2); pq = プッシュ(pq, 6, 3); pq = プッシュ(pq, 7, 0); while (isEmpty(pq) == 0) { console.log(peek(pq),' ');  pq = ポップ(pq); } // このコードは ishankhandelwals によって寄稿されました。>>

出力

 6 5 4 7>

詳細については、この記事を参照してください。

注記： リンクリストを使用することもできます。リンクリストを使用したすべての演算の時間計算量は配列と同じままです。リンクリストの利点は次のとおりです。 deleteHighestPriority() アイテムを移動する必要がないので、より効率的になります。

3) ヒープを使用して優先キューを実装します。

バイナリヒープは配列や LinkedList と比べてパフォーマンスが優れているため、プライオリティキューの実装には一般にバイナリヒープが推奨されます。ヒープの特性を考慮すると、最大のキーを持つエントリが一番上にあり、すぐに削除できます。ただし、残りのキーのヒーププロパティを復元するには O(log n) の時間がかかります。ただし、別のエントリをすぐに挿入する場合、この時間の一部は、新しいエントリの挿入に必要な O(log n) 時間と組み合わされる可能性があります。したがって、優先キューをヒープとして表現することは、連続ストレージ内で効率的に表現され、挿入と削除の両方に対数時間しか必要としないことが保証されるため、n が大きい場合に有利であることがわかります。バイナリヒープに対する操作は次のとおりです。

私からｐへ

バイナリヒープ	入れる（）	取り除く（）	ピーク（）
時間計算量フルフォームpvr	O(log n)	O(log n)	○(1)

バイナリヒープ

入れる（）

取り除く（）

ピーク（）

時間計算量

フルフォームpvr

O(log n)

○(1)

コードの実装については、この記事を参照してください。

4) 二分探索ツリーを使用して優先キューを実装します。

AVL ツリー、赤黒ツリーなどの自己平衡二分探索ツリーを使用して優先キューを実装することもできます。 Peak()、insert()、delete() などの操作は、BST を使用して実行できます。

二分探索木	ピーク（）	入れる（）	消去（）
時間計算量	○(1)	O(log n)	O(log n)

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

CPU スケジューリング
ダイクストラの最短経路アルゴリズム、プリムの最小スパニングツリーなどのグラフアルゴリズム。
スタックの実装
プライオリティキューのすべてのアプリケーション
C++ の優先キュー
Javaのプライオリティキュー
Python の優先キュー
JavaScriptのプライオリティキュー
Priority Queueに関する最近の記事！