C++とかPythonはいいよなぁー！！ 言語仕様に元々あってさあ！ C#にもあるけど競プロ用としてはちょっと使いにくいんだよねえ！！ デフォルトで最小ヒープだしインスタンス化の引数が2個あるし。手っ取り早くスッと使わせてもらえない感じ。いや必要十分ではあるか。
というわけで、二分ヒープの解説と実装をやっていきます。需要があるかどうかは知りません。
※競プロ用のため、解説に若干の偏見が含まれます。
まず概念の理解から
優先度付きキューにおいて重要なことはただ一つ。
- その中で最も高い優先度の要素を取得できる。
インデックスによるアクセスではなく、ただキューに「出して」と指示するだけで最も優先度の高い要素が取り出せること。
となると、キューに要素を追加した時点で優先度順に並び替える必要がある……と思うかもしれませんが、必ずしもそういうわけではありません。
優先度付きキューの仕様上、実際に全ての要素を優先度順に整列する必要はなく、その中で最も優先度の高い要素1つが分かればよいのです。
で、これを実現するためのデータ構造が二分ヒープとなります。
二分ヒープとは二分木構造であり、全ての親と子の要素同士は必ず順序の制約が満たされているデータ構造のことです。この制約上、一番上の段のルート（根）要素はその中で最大（あるいは最小）の要素であることが分かります。
他のデータ構造によるアプローチもありますが、大抵はこの二分ヒープにあれやこれやのメソッドやプロパティ（getter、setter）を追加して優先度付きキューとして扱います。
二分ヒープを使った優先度付きキューの仕様は以下の通り。
| 操作 | 計算量 |
| 要素の追加 | O(log N) |
| 先頭の参照 | O(1) |
| 先頭の削除（要素の取り出し） | O(log N) |
| 要素数の取得 | O(1) |
概念を理解できたので、この後は二分ヒープの実装とそこに優先度付きキューとしての振る舞いを追加します。
実装
優先度付きキュークラスを実装します。これに入れられる変数型はint型のみというシンプルな機能で利用できるようにします。
二分ヒープとして表現する変数の型はList<T>を使います。選定理由は可変長の配列が欲しいため。
変数型Tがintなど整数型であればそれをそのまま優先度として使えます1し、Listはインデックスでのアクセスが可能なので実装が簡便になります。
○ikipediaにもある通り、ルートを1として順番に番号を付けていくと、親と子の要素の関係に規則性があることが分かります。
C#もまた例によって配列のインデックスは0から始まりますが、二分ヒープにおいては1を基準として実装するほうが、要素の親や子の参照に使うインデックスの計算式を立てるのが楽になる2という利点があります。
そうしてその要素の親や子の値との比較をし、二分ヒープの制約を保つために要素の入れ替えを行うなどします。
優先度付きキューとして利用するために必要なメソッドは先ほど示しましたが以下の通り。（）内はメソッド名の例。
- 要素の追加（Push、Enqueue、Add）
- 先頭の参照（Peek）
- 先頭の削除（Pop、Dequeue）
- 要素数の取得（Count）
このクラスのインスタンスの外から利用可能なメソッドは以上で十分ですが、二分ヒープの制約を保つための処理も以下の通り必要です。
- 要素の追加時に親の要素と比較して再帰的に入れ替え（UpHeap、BubbleUp）
- 要素の削除時に子の要素と比較して再帰的に入れ替え（DownHeap、BubbleDown）
- （任意）親の要素のインデックスを計算する。
- （任意）右側の子、左側の子の要素のインデックスを計算する。
注意点として、要素の入れ替えは二分木のデータ構造に対する処理のため再帰的に呼び出す必要があります。
以上の処理が書ければ、あとはもうやることはないです。試しに動かしてみましょう。
躓きやすいところ
バブルダウン（down-heap）は条件の考慮不足によるバグを抱えやすいです。（2敗）
W○kipediaにもしれっと書いてありますが、子の要素との入れ替えはより大きい方を選びます（最大ヒープの場合）。でなければヒープの制約を満たせません。
その他、子の要素はインデックス外でないか、片方（左側）の要素だけある状況かどうか、それ以上何もしないか、それぞれ場合分けする必要があります。
計算量について
List<T>のRemoveAtメソッドの計算量はO(n)ですが末尾の削除に限りO(1)3となります。先頭の削除処理（Dequeue）の計算量は、二分ヒープ上でのルート（先頭）への代入や末尾の削除ではO(1)で済むため、バブルダウンの処理のO(logn)が残ります。
要素の追加処理でも同様に要素の比較及び交換がO(1)で済み、バブルアップを行う回数が木の高さ（世代数）と等しくなるので、これもO(logn)となります。
終わりに
ちょっと難しいとは思いますが、自力で実装してみると内部でどうなっているか、何が起こるか、何が必要なのかが想像できるので要件に合わせてアレンジしやすくなります。
追加で、最大ヒープか最小ヒープをインスタンス化時に選択できるようにすると問題毎に式を考えなくて済むのでちょっと楽ができますね。Funcとラムダ式、三項演算子辺りを使えば2行くらいで済みますし。
まあ今となっては「自力で実装しなくてもデフォルトで用意されてるやつ使えたなぁ～」と思うなど。いやまあ自力で実装したどシンプルな優先度付きキューの方が多少メモリ利用量が少なくなってた（-9%）からまあ多少は意味はあるけど……、多少は……。まあ勉強中だからね！
以上です。
- 問題及び仕様・制約・要件により異なる。 ↩︎
- C#においては0番目のデータはほとんど意味がなくなってしまうのと、計算したあとでデクリメントすればいいという考えもあります。実装する人間視点で何が楽かは人によって異なりますし、各自お好みで選択してください。 ↩︎
- 公式リファレンスより。https://learn.microsoft.com/ja-jp/dotnet/api/system.collections.generic.list-1.removeat?view=net-10.0 ↩︎
コメント