C# の優先キュー
Minahil Noor
2021年3月24日
Csharp

この記事では、C# で同等の優先キューを紹介します。
C# の優先キューとしてリスト
を使用する
C# では、優先キュー用の特別なクラスはありません。ただし、配列とリストを使用して実装できます。リストデータ構造を使用して、優先度付きキューを実装します。優先度付きキューは、その要素に関連付けられた優先度を持つ抽象データ型です。リストは、最高の優先順位が常に先頭になるように作成されます。リストを使用して優先キューを実装するためのアルゴリズムは次のとおりです。
PUSH(HEAD, VALUE, PRIORITY)
Step 1: Create a new node with VALUE and PRIORITY
Step 2: Check if HEAD has lower priority. If true follow Steps 3-4 and end. Else goto Step 5.
Step 3: NEW -> NEXT = HEAD
Step 4: HEAD = NEW
Step 5: Set TEMP to head of the list
Step 6: While TEMP -> NEXT != NULL and TEMP -> NEXT -> PRIORITY > PRIORITY
Step 7: TEMP = TEMP -> NEXT
[END OF LOOP]
Step 8: NEW -> NEXT = TEMP -> NEXT
Step 9: TEMP -> NEXT = NEW
Step 10: End
POP(HEAD)
Step 2: Set the head of the list to the next node in the list. HEAD = HEAD -> NEXT.
Step 3: Free the node at the head of the list
Step 4: End
TOP(HEAD):
Step 1: Return HEAD -> VALUE
Step 2: End
プッシュ操作は、優先度が最も高い要素が常に最上位になるように、要素を優先キューに追加します。pop 操作は、優先度が最も高い要素をキューから削除します。最上位の操作は、最も優先度の高い要素を削除せずに取得します。以下のプログラムは、優先度付きキューから要素をプッシュ、ポップ、および最上位にする方法を示しています。
using System;
class PriorityQueue
{
public class Node
{
public int data;
public int priority;
public Node next;
}
public static Node node = 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;
}
public static int top(Node head)
{
return (head).data;
}
public static Node pop(Node head)
{
Node temp = head;
(head) = (head).next;
return head;
}
public static Node push(Node head,
int d, int p)
{
Node start = (head);
Node temp = newNode(d, p);
if ((head).priority > p)
{
temp.next = head;
(head) = temp;
}
else
{
while (start.next != null &&
start.next.priority < p)
{
start = start.next;
}
temp.next = start.next;
start.next = temp;
}
return head;
}
public static int isEmpty(Node head)
{
return ((head) == null) ? 1 : 0;
}
public static void Main(string[] args)
{
Node queue = newNode(1, 1);
queue = push(queue, 9, 2);
queue = push(queue, 7, 3);
queue = push(queue, 3, 0);
while (isEmpty(queue) == 0)
{
Console.Write("{0:D} ", top(queue));
queue = pop(queue);
}
}
}
出力:
3 1 9 7
priority
の値が少ない要素ほど優先度が高くなります。