.NET 6 では、優先度付きキューを表す PriorityQueue<TElement,TPriority> クラスが基本クラスライブラリ (BCL) に追加されました。
言い換えると、.NET 5 以前の BCL には優先度付きキューが存在しません。
そこで、.NET 5 以前の環境において、平衡二分探索木のクラスを利用して優先度付きキューに相当する処理を実現する方法を考えてみます。
優先度付きキューの要件
まず、優先度付きキュー (priority queue) に必要な機能を整理します：
- Count: 現在の要素の数を取得する
- Peek: 優先度が最も高い要素を取得する。削除はしない
- Pop: 優先度が最も高い要素を取得し、同時に削除する
- Push: 新たな要素を追加する
すなわち、初めから全ての要素がわかっている (静的データ) とは限らず、要素の動的な追加に対応します。
また、オプション機能として次のものが考えられます：
- 一般的に、要素の重複を許す
- 昇順・降順を指定できる
- 要素に対して、優先度を表すキーを指定できる
- 安定ソート (一般的な二分ヒープでは不可)
例えば、1組の生徒たち、2組の生徒たち、・・・のような順でデータを取得する要件に対応するには、優先度を表すキーを指定できる機能があると便利です。
平衡二分探索木に関連するクラス
ここでは、.NET 5 以前の BCL に存在する平衡二分探索木およびその周辺のクラスについてまとめます。
以下の3種類があり、「追加した要素が自動的にキーの順序でソートされる」「キーの重複は不許可」という点はこれらに共通です。
なお、SortedList<TKey,TValue> クラスは平衡二分探索木ではありません (以降の節では使いません)。
(1) SortedSet<T> クラス
- 要素をキーとして使用する
- 要素の動的な追加および削除の時間計算量は O(log n)
- HashSet<T> が順序付きになったと考えてよい
(2) SortedDictionary<TKey,TValue> クラス
- キーと値のペアを格納する
- 要素の動的な追加および削除の時間計算量は O(log n)
- Dictionary<TKey,TValue> が順序付きになったと考えてよい
(3) SortedList<TKey,TValue> クラス
- キーと値のペアを格納する
- 通常のリストのような構造であり、空間計算量は O(n)
- 平衡二分探索木ではない
- 要素の動的な追加および削除の時間計算量は O(n)
- キーからインデックスの取得、インデックスから要素の取得の時間計算量は O(log n)
- ソート済みの静的データで初期化するだけの場合や、末尾にくるデータを追加するだけであれば速い
実装
では、平衡二分探索木を利用して、優先度付きキューを実装していきます。
要件に合わせて以下の3種類を用意しました。
(1) 要素を重複させない場合
- SortedSet<T> をほぼそのまま利用する
- Min プロパティおよび Add, Remove メソッドを呼び出せばよい
(2) 要素の重複を許す場合 (一般的な優先度付きキュー)
- SortedDictionary<T, int> を利用する
- 要素ごとの個数を管理する
(3) 要素に対して優先度を表すキーを指定する場合 (重複を許可)
- SortedDictionary<TKey, Queue<T>> を利用する
- キーごとにキューで要素を管理する
- したがって、安定ソートとなる
ソースコードは次の通りです。言語は C# です。
なお、降順を指定するには、前回の記事で作成した補助クラスで IComparer<T> を生成すればよいです。
| using System; | |
| using System.Collections.Generic; | |
| using System.Linq; | |
| namespace AlgorithmLab.DataTrees | |
| { | |
| // 要素が重複しない (すべての値の順序が異なる) 場合に利用できます。 | |
| public class DistinctPriorityQueue<T> | |
| { | |
| // 要素をそのままキーとして使用します。 | |
| SortedSet<T> ss; | |
| public DistinctPriorityQueue(IComparer<T> comparer = null) | |
| { | |
| ss = new SortedSet<T>(comparer ?? Comparer<T>.Default); | |
| } | |
| public int Count => ss.Count; | |
| public T Peek() | |
| { | |
| if (ss.Count == 0) throw new InvalidOperationException("The container is empty."); | |
| return ss.Min; | |
| } | |
| public T Pop() | |
| { | |
| if (ss.Count == 0) throw new InvalidOperationException("The container is empty."); | |
| var item = ss.Min; | |
| ss.Remove(item); | |
| return item; | |
| } | |
| public bool Push(T item) => ss.Add(item); | |
| } | |
| // 要素が重複する場合も利用できます (一般的な優先度付きキュー)。 | |
| public class BstPriorityQueue<T> | |
| { | |
| // 要素をそのままキーとして使用します。 | |
| SortedDictionary<T, int> sd; | |
| public BstPriorityQueue(IComparer<T> comparer = null) | |
| { | |
| sd = new SortedDictionary<T, int>(comparer ?? Comparer<T>.Default); | |
| } | |
| public int Count { get; private set; } | |
| public T Peek() | |
| { | |
| if (Count == 0) throw new InvalidOperationException("The container is empty."); | |
| return sd.First().Key; | |
| } | |
| public T Pop() | |
| { | |
| if (Count == 0) throw new InvalidOperationException("The container is empty."); | |
| Count--; | |
| var (item, count) = sd.First(); | |
| if (count == 1) sd.Remove(item); | |
| else sd[item] = count - 1; | |
| return item; | |
| } | |
| public void Push(T item) | |
| { | |
| Count++; | |
| sd.TryGetValue(item, out var count); | |
| sd[item] = count + 1; | |
| } | |
| } | |
| // 要素に対して優先度を表すキーを指定する場合に利用します。 | |
| public class KeyedPriorityQueue<T, TKey> | |
| { | |
| SortedDictionary<TKey, Queue<T>> sd; | |
| Func<T, TKey> keySelector; | |
| public KeyedPriorityQueue(Func<T, TKey> keySelector, IComparer<TKey> comparer = null) | |
| { | |
| this.keySelector = keySelector ?? throw new ArgumentNullException(nameof(keySelector)); | |
| sd = new SortedDictionary<TKey, Queue<T>>(comparer ?? Comparer<TKey>.Default); | |
| } | |
| public int Count { get; private set; } | |
| public T Peek() | |
| { | |
| if (Count == 0) throw new InvalidOperationException("The container is empty."); | |
| return sd.First().Value.Peek(); | |
| } | |
| public T Pop() | |
| { | |
| if (Count == 0) throw new InvalidOperationException("The container is empty."); | |
| Count--; | |
| var (key, q) = sd.First(); | |
| if (q.Count == 1) sd.Remove(key); | |
| return q.Dequeue(); | |
| } | |
| public void Push(T item) | |
| { | |
| Count++; | |
| var key = keySelector(item); | |
| if (!sd.TryGetValue(key, out var q)) sd[key] = q = new Queue<T>(); | |
| q.Enqueue(item); | |
| } | |
| } | |
| } |
また、平衡二分探索木を利用する利点として、優先度の高いほうだけでなく、両側に対する優先度付きキューを実現できることが挙げられます。PopFirst, PopLast メソッドとして作成すればよいでしょう。
利用例
(1) DistinctPriorityQueue
(2) BstPriorityQueue
(3) KeyedPriorityQueue
前回: ソート用の比較関数の補助クラス
作成したサンプル
検証したバージョン
- C# 8.0
- .NET Standard 2.1
Do Design Space 