C#, fastest PriorityQueue
After searching a lot and do my bench-marking I use this implementation which is faster than any PriorityQueue I\'ve seen. even faster than C5.IntervalHeap().\n
After searching a lot and do my bench-marking I use this implementation which is faster than any PriorityQueue I\'ve seen. even faster than C5.IntervalHeap().\n[my Submission](https://leetcode.com/submissions/detail/355137471/)\n```\n//A binary heap impelemntation\npublic class PriorityQueue<T> {\n    private readonly List<T> list;\n    private readonly IComparer<T> comparer;\n\t\n    public PriorityQueue(IComparer<T> comparer = null) {\n        this.comparer = comparer ?? Comparer<T>.Default;\n        this.list = new List<T>();\n    }\n\t//O(Log N)\n    public void Add(T x) {\n        list.Add(x);\n\t\t\n        var child = Count - 1;\n        while (child > 0){ // child index; start at end\n            int parent = (child - 1) / 2;// parent index\n            // child item is larger than (or equal) parent so we\'re done\n            if (comparer.Compare(list[parent], x) <= 0) break;\n            list[child] = list[parent];\n            child = parent;\n        }\n        if (Count > 0) list[child] = x;\n    }\n\n    public T Peek() => list[0];\n\t//O(Log N)\n    public T Poll() {\n        var ret = Peek();\n        var root = list[Count - 1];\n        list.RemoveAt(Count - 1);\n        var i = 0;//parent\n        while (i * 2 + 1 < Count) {\n            var left = 2 * i + 1; //left child\n            if (left > Count) break;  // no children so we\'re done\n            var right = 2 * i + 2; // right child\n            var c = right < Count && comparer.Compare(list[right], list[left]) < 0 ? right : left;\n            if (comparer.Compare(list[c], root) >= 0) break;\n            list[i] = list[c];\n            i = c;\n        }\n        if (Count > 0) list[i] = root;\n        return ret;\n    }\n\t\n    public int Count => list.Count;//Count is cached in List implelemtation\n\t\n    public void DisplayHeap() => list.ForEach(x => Console.WriteLine(x));\n}\n```\nand here\'s a usage of it:\n```\npublic class MedianFinder {\n\n    private readonly PriorityQueue<int> small;\n    private readonly PriorityQueue<int> large;\n    \n    public MedianFinder() {\n        var maxComparer = Comparer<int>.Create((x, y) => y.CompareTo(x));\n        small = new PriorityQueue<int>();\n        large = new PriorityQueue<int>(maxComparer);\n    }\n    \n   public void AddNum(int num) {\n        large.Add(num);\n        small.Add(large.Poll());\n        if (large.Count < small.Count)\n            large.Add(small.Poll());\n    }\n\n    public double FindMedian() {\n        return large.Count > small.Count\n           ? large.Peek()\n           : (large.Peek() + small.Peek()) / 2.0;\n    }\n}\n```\n\nIt\'s possible to implement PriorityQueue using a SortSet:\n```\n public class PQ {\n     private struct HeapKey{\n         public int Value;\n         public int Index;\n     }\n     \n    private readonly SortedSet<HeapKey> _set;\n    private int index;\n    public PQ(Comparer<int> comparer = null){\n        comparer = comparer ?? Comparer<int>.Default;\n        _set = new SortedSet<HeapKey>(\n            Comparer<HeapKey>.Create((x, y) => \n                        comparer.Compare(x.Value, y.Value) == 0 ?\n                        x.Index - y.Index :\n                        comparer.Compare(x.Value, y.Value))\n        );\n    }\n    \n    public void Add(int num){\n        _set.Add(new HeapKey{Value= num, Index = index++});\n    }\n    \n    public int Peek(){\n        return _set.First().Value;\n    }\n     \n     public int Pop(){\n         var item = _set.First();\n         _set.Remove(item);\n        return item.Value;\n    }\n     \n    public int Count => _set.Count;\n     \n }     \n```
['Binary Search', 'Heap (Priority Queue)']