優先度付きキューは、各要素に優先度を割り当てることで標準キューの機能を拡張する基本的なデータ構造です。要素が到着した順に処理されるFIFO（先入れ先出し）キューとは異なり、優先度付きキューは優先度に基づいて要素をデキュー（削除）します。常に最も優先度の高い要素が最初に処理されます。この優先順位付けは、数値（最小値または最大値）または任意のカスタム比較基準に基づいて行うことができます。
優先度付きキューは、重要度に基づいたタスクやイベントの効率的な管理が不可欠な多くのアルゴリズムやアプリケーションにおいて非常に役立ちます。例としては、以下のようなものがあります。
- 最短ジョブ優先（SJF）スケジューリング：オペレーティングシステムにおいて、推定実行時間に基づいてプロセスを効率的にスケジューリングします。
- 最良優先探索アルゴリズム（A*、Dijkstra）：ターゲットからの推定距離に基づいてノードに優先順位を付けることで、グラフ内の最適パスを見つけます。
- イベントシミュレーション：離散イベントシミュレーションでイベントを管理し、最も緊急度の高いイベントを最初に処理します。
- ヒープソート：ヒープ（優先度付きキューの特殊なタイプ）のプロパティを利用して効率的にソートを行うソートアルゴリズムです。
- ハフマン符号化：頻度に基づいてシンボルに優先順位を付けることで、効率的な圧縮アルゴリズムを構築します。
C#での優先度付きキューの実装
C#では、優先度付きキューをいくつか実装する方法があります。2つの一般的なアプローチを見てみましょう。
1. SortedSetの使用
組み込みのSortedSetクラスは、優先度付きキューを実装する便利な方法を提供します。SortedSetは要素を自動的にソートされた順序で維持するため、優先順位付けが簡素化されます。これは、要素の自然な順序（例：整数）によって優先度が暗黙的に決定される場合に特に便利です。
using System;
using System.Collections.Generic;
public class PriorityQueueSortedSet<T> where T : IComparable<T>
{
private SortedSet<T> _elements = new SortedSet<T>();
public void Enqueue(T item) => _elements.Add(item);
public T Dequeue()
{
if (_elements.Count == 0)
{
throw new InvalidOperationException("Priority queue is empty.");
}
T item = _elements.Min;
_elements.Remove(item);
return item;
}
public bool IsEmpty() => _elements.Count == 0;
public int Count => _elements.Count;
}
この実装は簡単ですが、そのパフォーマンスは基盤となるSortedSetによって制限され、エンキューとデキューの操作にO(log n)の複雑さがあります。特に大規模なデータセットでは、メモリ使用量も比較的大きくなる可能性があります。
2. 最小ヒープの実装
特に大規模なデータセットでは、パフォーマンスを向上させるために、カスタム最小ヒープの実装は大きな利点をもたらします。最小ヒープは、常に最小の要素がルートにあることを保証する二分木構造であり、エンキューとデキューの両方の操作にO(log n)の複雑さを実現します。SortedSetよりも実装は複雑ですが、最小ヒープは優れたパフォーマンスとメモリ管理のきめ細かい制御を提供します。
(最小ヒープの詳細な実装はこの記事の範囲外ですが、オンラインで多くのリソースがあります。)
実装の比較
| 機能 | SortedSet |
最小ヒープ |
|---|---|---|
| 使いやすさ | 簡単 | 難しい |
| エンキュー/デキューのパフォーマンス | O(log n) | O(log n) |
| メモリ使用量 | 潜在的に高い | 潜在的に低い |
| 柔軟性 | 低い | 高い |
適切な実装の選択
SortedSetとカスタム最小ヒープの最適な選択は、特定の要件によって異なります。SortedSetは、実装の容易さが極端なパフォーマンスの必要性を上回る、より単純なアプリケーションに最適です。パフォーマンスが重要なアプリケーションや大規模なデータセットの場合、カスタム最小ヒープの実装は速度とメモリ効率において大きな利点があります。