C# の優先キュー

Minahil Noor 2023年10月12日

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

C# の優先キューとしてリストを使用する

C# の優先キューとして`リスト`を使用する