Contents
二分ヒープと優先度付きキュー
プライオリティキュー（優先度付きキュー）とは、優先度の高いデータから取り出すというデータ構造で、その代表的なものがヒープといわれる木構造です。ヒープの中にも単純な構造である二分ヒープを扱います。
二分木は親ノードの番号を 2 倍して 1 または 2 を足したものが子ノードの番号となっています。そして（親の番号）番目の要素は（子の番号）番目の要素以下であるという条件が成り立っています。
データの追加
データを追加するときは数列の末尾に追加します。そして上記の条件が成り立つように下側から順に要素を入れ替える必要があるなら、一番上に到達するまで入れ替えを繰り返します。ただし途中で入れ替えなくてよくなったらそれ以降は要素を入れ替える必要はありません。
データの削除
データを取り除くときは数列の先頭の要素を取り除きます。そして新しい先頭の要素には数列の最後尾の値を割り当てます。そして条件が成り立つように上から順に要素を入れ替えていきます。このとき二つの子の要素が同じでどちらも親の要素より小さいときは、入れ替え後に同じ階層で入れ替えをする必要がないように値が小さいほうの子の要素と入れ替えます。この場合も途中で入れ替えの必要がない場合はそれ以降の処理は必要はありません。
で、こんなことをしてどのような意味があるのかですが、これをすることで値を取り出すときに値が小さい順に取り出すことができるようになるのです。値を格納するときにソートした状態で格納できればよいのですが、この方法なら計算量を減らすことができるのです。
C#には優先度付きキューとしてPriorityQueueがあります。これまではC#には標準で優先度付きキューの実装はなかったのですが、.NET 6から標準でサポートされることになりました。そのため車輪の再発明にしかならないのですが、二分ヒープと優先度付きキューを自分で実装してみることにします。
ここでは優先度を指定してデータを追加すること、データを取り出すときは優先度がもっとも高いものから取り出すことができるものを作ります。
PriorityQueueを実装してみる
データを格納するリストと優先度を格納するリストの2つを定義します。
|
1 2 3 4 5 6 7 8 |
using System; using System.Collections.Generic; public class MyPriorityQueue { List<int> _priorities = new List<int>(); List<object> _dataes = new List<object>(); } |
データの入れ替え
リスト内のデータを入れ替えるメソッドを定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class MyPriorityQueue { void SwapPriorities(int a, int b) { int c = _priorities[a]; _priorities[a] = _priorities[b]; _priorities[b] = c; } void SwapData(int a, int b) { object c = _dataes[a]; _dataes[a] = _dataes[b]; _dataes[b] = c; } } |
データの追加
優先度を指定してデータを格納するメソッドを定義します。priorityが小さいほうが「優先度が高い」とします。
まず最後にデータを追加して親のほうがpriorityの値が小さくなるようにデータを入れ替えます。途中で入れ替えの必要がなくなったら処理は終了です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
public class MyPriorityQueue { public void Push(object obj, int priority) { _priorities.Add(priority); _dataes.Add(obj); int lastNodeNumber = _priorities.Count - 1; while (true) { int parentNum = (lastNodeNumber - 1) / 2; if (_priorities[parentNum] > _priorities[lastNodeNumber]) { SwapPriorities(parentNum, lastNodeNumber); SwapData(parentNum, lastNodeNumber); } else break; lastNodeNumber = parentNum; if (parentNum == 0) break; } } } |
データの削除
データを取り出す処理を示します。二分木のルートを取り除き、最後尾のデータをルートに置きます。そして親のほうがpriorityの値が小さくなるようにデータを入れ替えます。途中で入れ替えの必要がなくなったら処理は終了です。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
public class MyPriorityQueue { public object Pop() { if (_priorities.Count == 1 || _priorities.Count == 2) { _priorities.RemoveAt(0); object ret0 = _dataes[0]; _dataes.RemoveAt(0); return ret0; } _priorities.RemoveAt(0); int rootPriority = _priorities[_priorities.Count - 1]; _priorities.RemoveAt(_priorities.Count - 1); _priorities.Insert(0, rootPriority); object ret = _dataes[0]; _dataes.RemoveAt(0); object rootObject = _dataes[_dataes.Count - 1]; _dataes.RemoveAt(_dataes.Count - 1); _dataes.Insert(0, rootObject); int parentNumber = 0; int leftNumber = 1; int rightNumber = _priorities.Count >= 3 ? 2 : -1; int count = _priorities.Count; while (true) { if (rightNumber != -1 && _priorities[parentNumber] > _priorities[leftNumber] && _priorities[parentNumber] > _priorities[rightNumber]) { if (_priorities[leftNumber] <= _priorities[rightNumber]) { SwapPriorities(parentNumber, leftNumber); SwapData(parentNumber, leftNumber); parentNumber = leftNumber; } else { SwapPriorities(parentNumber, rightNumber); SwapData(parentNumber, rightNumber); } } else if (_priorities[parentNumber] > _priorities[leftNumber]) { SwapPriorities(parentNumber, leftNumber); SwapData(parentNumber, leftNumber); } else if (rightNumber != -1 && _priorities[parentNumber] > _priorities[rightNumber]) { SwapPriorities(parentNumber, rightNumber); SwapData(parentNumber, rightNumber); } else return ret; leftNumber = parentNumber * 2 + 1; rightNumber = parentNumber * 2 + 2; if (leftNumber >= count) return ret; if (rightNumber >= count) rightNumber = -1; } } } |
要素の数
GetDataCountメソッドは優先キューのなかにデータが何個格納されているかを返します。
|
1 2 3 4 5 6 7 |
public class MyPriorityQueue { public int GetDataCount() { return _dataes.Count; } } |
実際に使ってみる
では実際に使ってみましょう。優先度を英単語に置き換えたものを追加し、そのあとデータが存在するかぎり、Priorityの値がもっとも小さいものを取り出してみます。実行結果をみてみるとたしかに値が小さい順に取り出せていることがわかります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Program { static void Main() { MyPriorityQueue queue = new MyPriorityQueue(); queue.Push("one", 1); queue.Push("five", 5); queue.Push("six", 6); queue.Push("ten", 10); queue.Push("two", 2); while (queue.GetDataCount() > 0) { string str = (string)queue.Pop(); Console.WriteLine(str); } } } |
