二分ヒープと優先度付きキュー

プライオリティキュー(優先度付きキュー)とは、優先度の高いデータから取り出すというデータ構造で、その代表的なものがヒープといわれる木構造です。ヒープの中にも単純な構造である二分ヒープを扱います。

二分木は親ノードの番号を 2 倍して 1 または 2 を足したものが子ノードの番号となっています。そして(親の番号)番目の要素は(子の番号)番目の要素以下であるという条件が成り立っています。

データの追加

データを追加するときは数列の末尾に追加します。そして上記の条件が成り立つように下側から順に要素を入れ替える必要があるなら、一番上に到達するまで入れ替えを繰り返します。ただし途中で入れ替えなくてよくなったらそれ以降は要素を入れ替える必要はありません。

データの削除

データを取り除くときは数列の先頭の要素を取り除きます。そして新しい先頭の要素には数列の最後尾の値を割り当てます。そして条件が成り立つように上から順に要素を入れ替えていきます。このとき二つの子の要素が同じでどちらも親の要素より小さいときは、入れ替え後に同じ階層で入れ替えをする必要がないように値が小さいほうの子の要素と入れ替えます。この場合も途中で入れ替えの必要がない場合はそれ以降の処理は必要はありません。

で、こんなことをしてどのような意味があるのかですが、これをすることで値を取り出すときに値が小さい順に取り出すことができるようになるのです。値を格納するときにソートした状態で格納できればよいのですが、この方法なら計算量を減らすことができるのです。

C#には優先度付きキューとしてPriorityQueueがあります。これまではC#には標準で優先度付きキューの実装はなかったのですが、.NET 6から標準でサポートされることになりました。そのため車輪の再発明にしかならないのですが、二分ヒープと優先度付きキューを自分で実装してみることにします。

ここでは優先度を指定してデータを追加すること、データを取り出すときは優先度がもっとも高いものから取り出すことができるものを作ります。

PriorityQueueを実装してみる

データを格納するリストと優先度を格納するリストの2つを定義します。

データの入れ替え

リスト内のデータを入れ替えるメソッドを定義します。

データの追加

優先度を指定してデータを格納するメソッドを定義します。priorityが小さいほうが「優先度が高い」とします。

まず最後にデータを追加して親のほうがpriorityの値が小さくなるようにデータを入れ替えます。途中で入れ替えの必要がなくなったら処理は終了です。

データの削除

データを取り出す処理を示します。二分木のルートを取り除き、最後尾のデータをルートに置きます。そして親のほうがpriorityの値が小さくなるようにデータを入れ替えます。途中で入れ替えの必要がなくなったら処理は終了です。

要素の数

GetDataCountメソッドは優先キューのなかにデータが何個格納されているかを返します。

実際に使ってみる

では実際に使ってみましょう。優先度を英単語に置き換えたものを追加し、そのあとデータが存在するかぎり、Priorityの値がもっとも小さいものを取り出してみます。実行結果をみてみるとたしかに値が小さい順に取り出せていることがわかります。