C#の優先度付きキュー（Priority Queue）の基本と実装方法

優先度付きキュー（Priority Queue）とは、各要素が「優先度」の値を持つデータ構造であり、通常のキューを拡張したものです。

通常のキューでは先入れ先出し（FIFO）で要素が処理されますが、優先度付きキューでは、要素を取り出す際に最も優先度の高い項目が最初に削除されます。この特性により、タスクスケジューリングやダイクストラ法などのアルゴリズムで広く活用されています。

優先度付きキューの基本的な定義方法

C#で優先度付きキューを実装するには、IComparable<T>インターフェースを実装したジェネリッククラスとして定義するのが一般的です。これにより、要素同士を比較して優先度を判定できるようになります。

public class MyPriorityQueue<T> where T : IComparable<T> {

}

要素の追加と内部データの保持

次に、キューへ要素を追加できるようにしていきます。以下の例では、内部にジェネリックリスト List<T> 型のフィールド info を用意し、そこに要素を格納しています。

コード例

public class MyPriorityQueue<T> where T : IComparable<T> {
    private List<T> info;

    public MyPriorityQueue() {
        this.info = new List<T>();
    }
}

.NET 6以降なら標準ライブラリが利用可能

なお、.NET 6以降では標準ライブラリとして System.Collections.Generic.PriorityQueue<TElement, TPriority> クラスが提供されています。独自実装を行う必要がない場合は、こちらを利用することで、ヒープ構造に基づいた効率的な優先度付きキューを手軽に扱うことができます。