【C#】優先度付きキュー(優先度付き待ち行列,priority queue)を実装してみる

はじめに

今回は優先度付きキューを実装してみようとという記事になります！

優先度付きキューを用いることで迷路での最短距離を求めるダイクストラ法などを実装することができます。

他の言語だと実装されているものもあるらしいのですが、C#にはないみたいなので自力で実装してみようと思います。

では早速みていきましょう。

優先度付きキューとは

優先度付きキューとはある優先度（例えば値の大きなものほど優先度が高いとか）に従って、 優先度の高いものから順に取り出すことの出来るコレクションのことです。

こうすることで値の挿入(エンキュー,プッシュ)・取り出し(デキュー,ポップ)は計算量、優先度が一番高い値の参照が計算量にすることができます。

二分木

優先度付きキューの細かい説明に入る前にまずは二分木について軽く触れておきましょう。

二分木とは根付き木構造の中で、あるノード（節点 node）が持つ子の数が高々2であるものをいいます。

二分木 - Wikipedia

これを応用して制約を追加したりと、いろんな応用例があるので是非これを機にマスターをしておくと良いかもしれません。

二分ヒープ

優先度付きキューの実装は二分ヒープを用います。

二分ヒープとは以下の制約をもつ二分木のことです。

• 要素間の順序関係に従った比較によって、各々のノードはそのノードの子よりも大きいか等しくなるように配置される（heap property）
• 木は完全にバランスの取れた二分木（すべての葉は同じ高さにある）になるか、木のもっとも高い方がすべて埋まっていないならば、ノードは左から右へ順に埋まっていく（shape property）

二分ヒープ - Wikipedia

また二分ヒープにはある要素の番号をnとすると以下のような性質があります。

• 親の番号は(n-1) / 2
• 左の子の番号は2n + 1
• 右の子の番号は2n + 2

これらの法則を保つためには要素を加えるとき(Push)・取り出すとき(Pop)に処理を加えなければなりません。

ここが理解できれば二分ヒープを理解したといっても過言ではないので頑張ってみていきましょう。

要素を加える(Push)

要素を加えるときは以下の手順で操作を行います。

1. ヒープの最下層に要素を追加する
2. 追加した要素とその親を比較する。正しい順序で並んでいるならば、停止する
3. もし順序が正しくないならば、親と追加要素を交換して、2に戻る

二分ヒープ - Wikipedia

これをコードで書いてみましょう。

public void Push(T item)
{
    _array[this.Count] = item;          // ヒープの最下層に要素を追加する
    Count += 1;

    var n = Count - 1;                  // 末尾(追加した)のノードの番号
    while (n != 0)
    {
        var parent = (n - 1) / 2;       // 親ノードの番号

        // 追加した要素とその親を比較し、正しい順序でなければ入れ替える
        if (Compare(_array[n], _array[parent]) > 0)
        {
            Swap(n, parent);
            n = parent;
        }
        else
        {
            break;
        }
    }
}

要素を取り出す(Pop)

要素を取り出すときには以下の操作を行います。

1. ヒープのルート(一番上の奴)に末端の値をコピーし、末端を削除
2. ルートとその子を比較し、正しい順序で並んでいるならば、停止する
3. もし正しい順序でなければ優先度が高い(値が大きい等)子と交換し2に戻る

public T Pop()
{
    Swap(0, this.Count - 1);            // 先頭要素を末尾にする
    Count -= 1;

    var parent = 0;                     // 親ノードの番号
    while (true)
    {
        var child = 2 * parent + 1;     // 子ノードの番号
        if (child > Count - 1) break;

        // 値の大きい方の子を選ぶ
        if (child < Count - 1 && Compare(_array[child], _array[child + 1]) < 0) child += 1;

        // 子の方が親より大きければ入れ替える
        if (Compare(_array[parent], _array[child]) < 0)
        {
            Swap(parent, child);
            parent = child;
        }
        else
        {
            break;
        }
    }

    return _array[Count];
}

実装

これらのコードを組み合わせて優先度付きキューを実装してみました。

PriorityQueue.cs

using System;
using System.Collections;
using System.Collections.Generic;

class PriorityQueue<T> where T : IComparable<T>
{
    private readonly T[] _array;
    private readonly IComparer _comparer;
    public int Count { get; private set; } = 0;
    public T Root => _array[0];

    public PriorityQueue(int capacity, IComparer comparer = null)
    {
        _array = new T[capacity];
        _comparer = comparer;
    }

    /// <summary>
    /// 要素を挿入する
    /// </summary>
    public void Push(T item)
    {
        _array[this.Count] = item;
        Count += 1;

        var n = Count - 1;                  // 末尾(追加した)のノードの番号
        while (n != 0)
        {
            var parent = (n - 1) / 2;       // 親ノードの番号

            if (Compare(_array[n], _array[parent]) > 0)
            {
                Swap(n, parent);
                n = parent;
            }
            else
            {
                break;
            }
        }
    }

    /// <summary>
    /// 優先度の一番高いものを取り出す
    /// </summary>
    public T Pop()
    {
        Swap(0, this.Count - 1);            // 先頭要素を末尾にする
        Count -= 1;

        var parent = 0;                     // 親ノードの番号
        while (true)
        {
            var child = 2 * parent + 1;     // 子ノードの番号
            if (child > Count - 1) break;

            // 値の大きい方の子を選ぶ
            if (child < Count - 1 && Compare(_array[child], _array[child + 1]) < 0) child += 1;

            // 子の方が親より大きければ入れ替える
            if (Compare(_array[parent], _array[child]) < 0)
            {
                Swap(parent, child);
                parent = child;
            }
            else
            {
                break;
            }
        }

        return _array[Count];
    }

    /// <summary>
    /// 大きいものから列挙していく
    /// withPop = falseのときは順番関係なく取り出しもしないが素早く全要素を取得できる　
    /// </summary>
    public IEnumerable<T> GetAllElements(bool withPop = true)
    {
        int count = Count;
        for (int i = 0; i < count; i++)
        {
            if (withPop) yield return Pop();
            else yield return _array[count - i - 1];
        }
    }

    private int Compare(T a, T b)
    {
        if (_comparer == null) return a.CompareTo(b);
        return _comparer.Compare(a, b);
    }

    private void Swap(int a, int b)
    {
        var tmp = _array[a];
        _array[a] = _array[b];
        _array[b] = tmp;
    }
}

使い方

使う時はこんな感じ。

static void Main(string[] args)
{
    var q = new PriorityQueue<long>(10);

    // 1~10の値をランダムで実行していく
    foreach (var item in Enumerable.Range(1, 10).OrderBy(t => Guid.NewGuid()))
    {
        // 値を挿入する
        q.Push(item);
    }

    // 10個の要素から最大値を参照する
    var max = q.Root;
    Console.WriteLine(max);         // 10

    // 10個の要素から最大値を取り出す
    max = q.Pop();
    Console.WriteLine(max);         // 10

    // 9個の要素から最大値をどんどん取り出す
    foreach (var item in q.GetAllElements())
    {
        Console.WriteLine(item);    // 9 8 7 6 5 4 3 2 1
    }
}

基本は値が大きいほど優先度が高い，つまりPopメソッドで最大値がとれるような最大ヒープになっています。

ただ優先度を自分で設定できるようにしたので、もし降順にした場合は以下のようにしてください。

// 比較の方法を変える
var q = new PriorityQueue<long>(10, Comparer<long>.Create((x, y) => (int)(y - x)));

さいごに

こういうアルゴリズム系をそこそこしっかり書こうと思うとやっぱり大変ですね。

文字数的にはコードとかを含めて6600文字くらいなのでまだそこまでですが、他の記事に比べて使う労力が2倍くらいある気がします。

まあプログラミングをする上でこういった基礎知識は大切だと思うのでぼちぼち続けていきたいと思います。

ではまた。