包含异步多线程的优先队列

PriorityQueue.cs

    /// <summary>
    /// 优先队列
    /// </summary>
    /// <typeparam name="T">队列内容的类</typeparam>
    public class PriorityQueue<T>
    {
        const int TOPINDEX = 1;

        private List<T> heap;
        private Comparison<T> compare;
        private Task sortTask;

        public PriorityQueue(Comparison<T> compare)
        {
            heap = new List<T>(10);
            heap.Add(default(T));
            this.compare = compare;
        }

        /// <summary>
        /// 将ts中的数据构造成优先队列
        /// </summary>
        /// <param name="ts">原始数据</param>
        public PriorityQueue(Comparison<T> compare, IReadOnlyCollection<T> ts): this(compare)
        {
            PushAsyn(ts, null);
        }

        private void _adjust()
        {
            for (int i = (heap.Count - 1) / 2; i >= 1; i--)
            {
                _adjustDown(i);
            }
        }

        private void Sort(IReadOnlyCollection<T> ts, Action<Task> continueWith) 
        {
            sortTask = new Task(() => { heap.AddRange(ts); _adjust(); });
            if (continueWith is not null)
            {
                sortTask.ContinueWith(continueWith);
            }
            sortTask.Start();
        } 

        private void Wait()
        {
            if (sortTask is not null && sortTask.Status != TaskStatus.RanToCompletion)
            {
                sortTask.Wait();
            }
        }

        public void PushAsyn(IReadOnlyCollection<T> objs)
        {
            PushAsyn(objs, null);   
        }

        public void PushAsyn(IReadOnlyCollection<T> objs, Action<Task> continueWith)
        {
            Wait();
            Sort(objs, continueWith);
        }

        public void Pop()
        {
            Wait();
            top = rear;
            heap.RemoveAt(heap.Count - 1);
            _adjustDown(TOPINDEX);
        }

        public void Push(T obj)
        {
            Wait();
            heap.Add(obj);
            _adjustUp(heap.Count - 1);
        }

        public bool Empty()
        {
            if (heap.Count > 1) return false;
            else return true;
        }

        public T Front
        {
            get
            {
                Wait();
                return top;
            }
        }

        private T top
        {
            get
            {
                return heap[TOPINDEX];
            }
            set
            {
                heap[TOPINDEX] = value;
            }
        }

        private T rear
        {
            get
            {
                return heap[heap.Count - 1];
            }
            set
            {
                heap[heap.Count - 1] = value;
            }
        }

        private void _adjustDown(int par)
        {
            int child;
            for (int i = par; i * 2 < heap.Count; i = child)
            {
                child = i * 2;

                if (child + 1 < heap.Count && compare.Invoke(heap[child + 1], heap[child]) > 0)
                {
                    child++;
                }

                if (compare.Invoke(heap[child], heap[i]) > 0)
                {
                    T temp = heap[child];
                    heap[child] = heap[i];
                    heap[i] = temp;
                }
                else break;
            }
        }

        private void _adjustUp(int child)
        {
            int parent;
            for (int i = child; i / 2 >= 1; i = parent)
            {
                parent = i / 2;
                if (!(compare.Invoke(heap[parent], heap[i]) > 0))
                {
                    T temp = heap[parent];
                    heap[parent] = heap[i];
                    heap[i] = temp;
                }
                else break;
            }
        }
    }