つーさのくーかん

Dijkstra とか教科書通りに書きたいとき。コピペしていいプロコン用に。

public class PriorityQueue<T> {
    List<T> list = new List<T>();
    IComparer<T> comp = Comparer<T>.Default;
    class Comparer : IComparer<T> {
        Comparison<T> comparison;
        public Comparer(Comparison<T> comparison) { this.comparison = comparison; }
        public int Compare(T x, T y) { return comparison(x, y); }
    }
    public PriorityQueue() { }
    public PriorityQueue(Comparison<T> comp) { this.comp = new Comparer(comp); }
    public void Enqueue(T item) { int i = list.BinarySearch(item, comp); list.Insert(i < 0 ? ~i : i, item); }
    public T Dequeue() { T r = list[0]; list.RemoveAt(0); return r; }
    public T Peek() { return list[0]; }
    public int Count { get { return list.Count; } }
    public T this[int i] { get { return list[i]; } set { list[i] = value; } }
}

public class Program { // てすと
    class A : IComparable<A> {
        public int X;
        public A(int x) { this.X = x; }
    }

    static void Main() {
        PriorityQueue<A> Q = new PriorityQueue<A>((x, y) => y.X - x.X); // でかい順
        Q.Push(new A(1));
        Q.Push(new A(3));
        Q.Push(new A(2));
        Q.Push(new A(1));

        Console.WriteLine(Q.Pop().X);
        Console.WriteLine(Q.Pop().X);
        Console.WriteLine(Q.Pop().X);
        Console.WriteLine(Q.Pop().X);
    }
}

中の構造に単純な配列を使ってるのでPushとPopでメモリコピーが発生してO(N)なのがどうかなー。
状態数が多くなるならちゃんとヒープ作るべきなのかも。

SortedList は、キーが重複できないのでいやーんな感じ。
つーか、もうちょっとスニペットを充実させておきたいなぁ。