Priority Queue Comparison

    public class PriorityQueue<TK, TV>
    {
        private readonly SortedDictionary<TK, Queue<TV>> _D = new SortedDictionary<TK, Queue<TV>> ();

        public void Enqueue (TK key, TV value)
        {
            Queue<TV> list;
            if (!_D.TryGetValue (key, out list)) {
                list = new Queue<TV> ();
                _D.Add (key, list);
            }
            list.Enqueue (value);
            Count++;
        }

        public int Count
        {
            get;
            private set;
        }

        public TV Dequeue ()
        {
            var first = _D.First ();
            var item = first.Value.Dequeue ();
            if (!first.Value.Any ()) {
                _D.Remove (first.Key);
            }
            return item;
        }

        public IEnumerable<TV> Values
        {
            get
            {
                var keys = _D.Keys.ToArray ();
                foreach (var key in keys) {
                    var items = _D[key];
                    foreach (var item in items) {
                        yield return item;
                    }
                }
            }
        }
    }




    public class PriorityQueueD<TK, TV>
    {
        private readonly Dictionary<TK, Queue<TV>> _D = new Dictionary<TK, Queue<TV>> ();

        public void Enqueue (TK key, TV value)
        {
            Queue<TV> list;
            if (!_D.TryGetValue (key, out list)) {
                list = new Queue<TV> ();
                _D.Add (key, list);
            }
            list.Enqueue (value);
            Count++;
        }

        public int Count
        {
            get;
            private set;
        }

        private bool HasMin = false;
        private TK Min = default (TK);

        public TV Dequeue ()
        {
            if (!HasMin) {
                Min = _D.Keys.Min ();
                HasMin = true;
            }
            var items = _D[Min];
            var item = items.Dequeue ();
            if (!items.Any ()) {
                _D.Remove (Min);
                HasMin = false;
            }
            return item;
        }

        public IEnumerable<TV> Values
        {
            get
            {
                var keys = _D.Keys.ToArray ();
                Array.Sort (keys);
                foreach (var key in keys) {
                    var items = _D[key];
                    foreach (var item in items) {
                        yield return item;
                    }
                }
            }
        }
    }





    internal class PriorityQueueTest
    {
        private class Point
        {
            public readonly int ImplId;
            public readonly int Items;
            public readonly int Buckets;
            public readonly double? TimeAdd;
            public readonly double? TimeDeq;
            public readonly double? TimeEnu;

            public Point (int implId, int items, int buckets)
            {
                ImplId = implId;
                Items = items;
                Buckets = buckets;

                Stopwatch sw;

                if (implId == 0) {
                    try {
                        var dic = new OrderedMultiDictionary<int, int> (true);

                        sw = Stopwatch.StartNew ();
                        for (int i = 0; i < Items; i++) {
                            dic.Add (i * i % Buckets, i);
                        }
                        sw.Stop ();
                        TimeAdd = Math.Log (sw.Elapsed.TotalMilliseconds, 2);

                        sw = Stopwatch.StartNew ();
                        foreach (var v in dic.Values) {
                            var dummy = v;
                        }
                        sw.Stop ();
                        TimeEnu = Math.Log (sw.Elapsed.TotalMilliseconds, 2);

                        // TODO: TimeDeq

                        TimeDeq = null;
                    }
                    catch (OutOfMemoryException) {
                        TimeAdd = TimeDeq = TimeEnu = null;
                    }
                }
                else if (implId == 1) {
                    try {
                        var pq = new PriorityQueue<int, int> ();

                        sw = Stopwatch.StartNew ();
                        for (int i = 0; i < Items; i++) {
                            pq.Enqueue (i * i % Buckets, i);
                        }
                        sw.Stop ();
                        TimeAdd = Math.Log (sw.Elapsed.TotalMilliseconds, 2);

                        sw = Stopwatch.StartNew ();
                        foreach (var v in pq.Values) {
                            var dummy = v;
                        }
                        sw.Stop ();
                        TimeEnu = Math.Log (sw.Elapsed.TotalMilliseconds, 2);

                        sw = Stopwatch.StartNew ();
                        for (int i = 0; i < Items; i++) {
                            int dummy = pq.Dequeue ();
                        }
                        sw.Stop ();
                        TimeDeq = Math.Log (sw.Elapsed.TotalMilliseconds, 2);
                    }
                    catch (OutOfMemoryException) {
                        TimeAdd = TimeDeq = TimeEnu = null;
                    }
                }
                else {
                    try {
                        var pq = new PriorityQueueD<int, int> ();

                        sw = Stopwatch.StartNew ();
                        for (int i = 0; i < Items; i++) {
                            pq.Enqueue (i * i % Buckets, i);
                        }
                        sw.Stop ();
                        TimeAdd = Math.Log (sw.Elapsed.TotalMilliseconds, 2);

                        sw = Stopwatch.StartNew ();
                        foreach (var v in pq.Values) {
                            var dummy = v;
                        }
                        sw.Stop ();
                        TimeEnu = Math.Log (sw.Elapsed.TotalMilliseconds, 2);

                        if (Items > 1000 * 1000) {
                            TimeDeq = null;
                        }
                        else {
                            sw = Stopwatch.StartNew ();
                            for (int i = 0; i < Items; i++) {
                                int dummy = pq.Dequeue ();
                            }
                            sw.Stop ();
                            TimeDeq = Math.Log (sw.Elapsed.TotalMilliseconds, 2);
                        }
                    }
                    catch (OutOfMemoryException) {
                        TimeAdd = TimeDeq = TimeEnu = null;
                    }
                }
            }

            public override string ToString ()
            {
                var s = "";
                if (TimeAdd == null) {
                    s += " n/a";
                }
                else {
                    s += TimeAdd.Value.ToString ("0.0").PadLeft (4);
                }
                s += " / ";
                if (TimeEnu == null) {
                    s += " n/a";
                }
                else {
                    s += TimeEnu.Value.ToString ("0.0").PadLeft (4);
                }
                s += " / ";
                if (TimeDeq == null) {
                    s += " n/a";
                }
                else {
                    s += TimeDeq.Value.ToString ("0.0").PadLeft (4);
                }
                return s;
            }
        }

        private static List<Point> pts = new List<Point> ();

        public static void Test ()
        {
            for (int i = 1; i <= 1000 * 1000 * 100; i *= 2) {
                for (int buckets = 0; buckets <= 4; buckets++) {
                    for (int id = 0; id <= 2; id++) {
                        pts.Add (new Point (id, i, (int) Math.Pow (32, buckets)));
                        Draw ();
                    }
                }
            }
        }

        private static void Draw ()
        {
            GC.Collect (2);
            Console.Clear ();

            var xs = pts.Select (p => p.Buckets).Distinct ();
            var ys = pts.Select (p => p.Items).Distinct ();

            Console.Write ("".PadLeft (10));
            Console.Write ("| ");
            foreach (var x in xs) {
                Console.Write (x.ToString ().PadLeft (11));
                Console.Write ("        | ");
            }
            Console.WriteLine ();
            Console.WriteLine ();

            foreach (var y in ys.Where (v => v > 100)) {
                Console.Write (y.ToString ().PadLeft (10));
                Console.WriteLine ();

                for (int id = 0; id <= 2; id++) {
                    Console.Write ("".PadLeft (10));
                    Console.Write ("| ");

                    foreach (var x in xs) {
                        var select = pts
                            .Where (p => p.ImplId == id)
                            .Where (p => p.Buckets == x && p.Items == y)
                            .FirstOrDefault ();
                        if (select == null) {
                            Console.Write ("  ?  /   ?  /   ? ");
                        }
                        else {
                            Console.Write (select);
                        }
                        Console.Write (" | ");
                    }
                    Console.WriteLine ();
                }

                Console.WriteLine ();
                Console.WriteLine ();
            }
        }
    }