C#实现优先队列模板

        C#并不提供优先队列这个API。所以我们要自己去实现C#的优先队列。这里我参考了知乎这位作者的优先队列实现。（不过他用的是C++,我只是单纯的转换为C#而言）文章链接：https://zhuanlan.zhihu.com/p/35314095。具体的方法可以直接去看知乎的文章。我这里就直接给出C#的实现。（这里我根据自己的需求加了一些东西，你们也可以看文章中的代码改造然后根据自己的需求去修改）

using System;
using System.Linq;

namespace ConsoleApp1
{
    public class PriorityQueue<T> where T : IComparable
    {
        private int count;//当前数量
        private T[] queue;//队列数组
        private Func<T, T, bool> cmp;//比较函数
        private int capacity;//容量
        private const int DefalutCapacity = 100;//默认容量

        public int Count { get { return count; } }

        public PriorityQueue() : this(DefalutCapacity, null) { }

        public PriorityQueue(Func<T, T, bool> cmp) : this(DefalutCapacity, cmp) { }

        public PriorityQueue(int capacity, Func<T, T, bool> cmp)
        {
            this.cmp = cmp;
            this.capacity = capacity;
            queue = new T[capacity];
            count = 0;
        }

        ~ PriorityQueue()
        {

        }

        //获取队首
        public T Peek()
        {
            //队列为空则报错
            if(count == 0)
            {
                throw new InvalidOperationException("队列为空");
            }
            return queue[1];
        }

        //插入数据
        public void Enqueue(T val)
        {
            count++;
            //当容量不足时扩充容量
            if(capacity == count)
            {
                //当所需求的容量太大，则抛出异常
                if (int.MaxValue == capacity)
                {
                    throw new ArgumentOutOfRangeException("count");
                }
                //当容积翻倍过大的时候，让其等于最大值
                if(int.MaxValue - capacity < capacity)
                {
                    capacity = int.MaxValue;
                }
                else
                {
                    //容积翻倍
                    capacity *= 2;
                }
                //新建立一个数组
                T[] tmp = new T[capacity];
                //复制元数组中的内容
                for (int i = 0; i < count; i++)
                {
                    tmp[i] = queue[i];
                }
                //将新建立的数组作为队列
                queue = tmp;
            }
            //直接在尾部添加新数据
            queue[count] = val;
            //上浮操作，让新添加的数据到达它应该存储的位置
            Swim(count);
        }

        //删除队首
        public T Dequeue()
        {
            //如果队列此时为空则报错
            if(count == 0)
            {
                throw new InvalidOperationException("队列为空");
            }
            //直接输出队首，并将队尾数据覆盖队首
            T res = queue[1];
            queue[1] = queue[count];
            count--;
            //下沉操作，然队列仍为优先队列
            Sink(1);
            return res;
        }

        public bool isEmpty()
        {
            return count == 0;
        }

        public T[] ToArray()
        {
            return queue.ToArray();
        }

        private void Swim(int n)
        {
            while (n > 1)
            {
                T val1 = queue[n];
                //获取其父亲的值，并与之比较
                T val2 = queue[n >> 1];
                //满足条件交换数据
                if(CompareFun(val1,val2))
                {
                    queue[n] = val2;
                    queue[n >> 1] = val1;
                }
                n = n >> 1;
            }
        }

        private void Sink(int n)
        {
            while(2 * n <= count)
            {
                int t = 2 * n;
                if (t < count && CompareFun(queue[t + 1], queue[t])) t++;
                if (CompareFun(queue[t], queue[n]))
                {
                    T tmp = queue[t];
                    queue[t] = queue[n];
                    queue[n] = tmp;
                    n = t;
                }
                else break;
            }
        }

        //判断大小
        private bool CompareFun(T val1, T val2)
        {
            //如果用户有自定义函数则使用用户定义的函数
            if (cmp != null)
            {
                return cmp(val1, val2);
            }
            //默认为大堆
            return val1.CompareTo(val2) > 0;
        }
    }
}