C# の優先キュー

この記事では、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 の値が少ない要素ほど優先度が高くなります。