優先順位つきキュー

ソース長いので

優先順位つきキューと二分ヒープのセット。

Verifyはまだしてない。

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

namespace TopCoderLib
{
    public static partial class Algorithm
    {
        /// <summary>
        /// 二分ヒープを表します
        /// </summary>
        /// <typeparam name="T">ヒープに格納されるデータの型</typeparam>
        public class Heap<T>
            where T : IComparable<T>
        {
            private T[] array;
            private static T[] empty = null;
            private int size;
            private Compare cmp;

            /// <summary>
            /// 整列のために要素を比較する際に用いるデリゲートです
            /// </summary>
            /// <param name="a">比較する値</param>
            /// <param name="b">比較する値</param>
            /// <returns>a > bなら正数、a == bなら0、a <![CDATA[<]]> bなら負数を返します</returns>
            public delegate int Compare(T a, T b);

            /// <summary>
            /// このヒープに格納されている要素の数を表します
            /// </summary>
            public int Count { get { return size; } }

            /// <summary>
            /// このヒープに格納されている値をインデックスを使って取得します。
            /// ルート要素を取得するには0を指定してください。他の場合はIndexOfメソッドと併せて使用してください。
            /// </summary>
            /// <param name="index">取得したい値のインデックス</param>
            public T this[int index] { get { return array[index]; } }

            /// <summary>
            /// 新しいヒープを生成します。
            /// </summary>
            public Heap()
            {
                array = empty;
                size = 0;
                cmp = delegate(T a, T b) { return a.CompareTo(b); };
            }

            /// <summary>
            /// 与えられた数のぶんだけ要素を格納できる新しいヒープを生成します。
            /// 必要があればヒープはInsertメソッドによって自動的に拡張されます。
            /// </summary>
            /// <param name="capacity">確保する領域の大きさ</param>
            public Heap(int capacity)
            {
                array = new T[capacity];
                size = 0;
                cmp = delegate(T a, T b) { return a.CompareTo(b); };
            }

            /// <summary>
            /// データの比較方法を指定した新しいヒープを生成します。
            /// </summary>
            /// <param name="compare">二つのデータを比較するデリゲート</param>
            public Heap(Compare compare)
            {
                array = empty;
                size = 0;
                cmp = compare;
            }

            /// <summary>
            /// データの比較方法を指定して、与えられた数の分だけ要素を格納できる新しいヒープを生成します。
            /// </summary>
            /// <param name="compare">二つのデータを比較するデリゲート</param>
            public Heap(int capacity, Compare compare)
            {
                array = new T[capacity];
                size = 0;
                cmp = compare;
            }

            /// <summary>
            /// ヒープに要素を追加します。必要があればヒープは自動的に拡張されます。
            /// </summary>
            /// <param name="data">追加するデータ</param>
            public void Insert(T data)
            {
                if (array == empty || array.Length == size)
                {
                    T[] dest = new T[(array == empty) ? 4 : (2 * array.Length)];
                    if(array != empty)
                        Array.Copy(array, dest, array.Length);
                    array = dest;
                }
                int n = ++size;
                array[n - 1] = data;
                while (n != 1 && cmp(array[n / 2 - 1], array[n - 1]) > 0)
                {
                    int i = n / 2 - 1, j = n - 1;
                    T tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                    n /= 2;
                }
            }

            /// <summary>
            /// ルート要素を削除します
            /// </summary>
            /// <returns>削除される前のルート要素を返します</returns>
            public T RemoveRoot()
            {
                T res = array[0];
                array[0] = array[--size];

                int i = 0;
                while (2 * i < size)
                {
                    int j = 2 * i + 1;
                    if (j < size && cmp(array[j], array[j + 1]) > 0)
                        ++j;
                    if (cmp(array[i], array[j]) > 0)
                    {
                        T tmp = array[i];
                        array[i] = array[j];
                        array[j] = tmp;
                    }
                    else { break; }
                    i = j;
                }

                return res;
            }

            /// <summary>
            /// 指定されたデータがこのヒープのどこにあるか探索します
            /// </summary>
            /// <param name="data">探索するデータ</param>
            /// <returns>データのあるインデックス</returns>
            public int IndexOf(T data)
            {
                for (int i = 0; i < size; ++i)
                    if (cmp(array[i], data) == 0)
                        return i;
                return -1;
            }
        }

        /// <summary>
        /// 優先順位つきキューを表します
        /// </summary>
        /// <typeparam name="T">優先順位つきキューに格納するデータの型</typeparam>
        public class PriorityQueue<T>
            where T : IComparable<T>
        {
            private Heap<T> heap;

            /// <summary>
            /// このキューに格納されている要素の数を表します
            /// </summary>
            public int Count { get { return heap.Count; } }

            /// <summary>
            /// 新しい優先順位つきキューを生成します
            /// </summary>
            public PriorityQueue()
            {
                heap = new Heap<T>();
            }

            /// <summary>
            /// 既定の初期値を格納する新しい優先順位つきキューを生成します
            /// </summary>
            /// <param name="data">はじめに保持するデータ</param>
            public PriorityQueue(IEnumerable<T> data)
            {
                heap = new Heap<T>();
                foreach (T v in data)
                {
                    heap.Insert(v);
                }
            }

            /// <summary>
            /// 比較の方法を指定して、新しい優先順位つきキューを生成します
            /// </summary>
            /// <param name="cmp">比較に用いるデリゲート</param>
            public PriorityQueue(Heap<T>.Compare cmp)
            {
                heap = new Heap<T>(cmp);
            }

            /// <summary>
            /// 比較の方法を指定して、既定の初期値を格納する新しい優先順位つきキューを生成します
            /// </summary>
            /// <param name="data">はじめに保持するデータ</param>
            /// <param name="cmp">比較に用いるデリゲート</param>
            public PriorityQueue(IEnumerable<T> data, Heap<T>.Compare cmp)
            {
                heap = new Heap<T>(cmp);
                foreach (T v in data)
                {
                    heap.Insert(v);
                }
            }

            /// <summary>
            /// この優先順位つきキューに要素を追加します
            /// </summary>
            /// <param name="data">追加するデータ</param>
            public void Enqueue(T data)
            {
                heap.Insert(data);
            }

            /// <summary>
            /// この優先順位つきキューから要素を取り出します
            /// </summary>
            /// <returns>取り出されたデータ</returns>
            public T Dequeue()
            {
                return heap.RemoveRoot();
            }
        }
    }
}