C#最优队列最小堆小顶堆大顶堆小根堆大根堆PriorityQueue的使用

本文主要是介绍C#最优队列最小堆小顶堆大顶堆小根堆大根堆PriorityQueue的使用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最优队列有多种叫法，什么小根堆，大根堆，小顶堆，大顶堆。

队列分多种，线性队列（简单队列），循环队列，最优队列等等。

最优队列，可以看作堆叠箱子，越小的越在上面，或者最大的越在上面。目的就是求出前面最值。比如最大的前3个，或最小的前3个。

framework中只能自己创建类，或者变通由sortedset等来做，现在.net6及以后有了。

下面由.net8（反正它也长期被支持了，就用它吧）。

PriorityQueue定义时要指明两个，前者是元素（对象），后者是优先级，一般是整型，如果是自定义类型，需要对这个优先级自己再定义一个比较器，以便最优队列根据这个比较得知哪个“最优”（最大或最小）。

下面创建多个结构体变量，用大量的数来入队，选取前4个（根据结构体的成员value)。

由于选4个前4个最大值，因此我们设置5为最大容量。满4后就要开始考虑出队问题。

第一种: 满4后，是先判断顶点后入队，还是直接入队出队，这两者哪个效率更优？简单测试一下：

    public struct RecSample{public int Name { get; set; }public int Value { get; set; }}//public class RecCompare : IComparer<RecSample>//{//    public int Compare(RecSample x, RecSample y)//    {//        return x.Value.CompareTo(y.Value);//    }//}internal class Program{private static void Main(string[] args){Random r = new Random();List<RecSample> list = new List<RecSample>();for (int i = 0; i < 30; i++){list.Add(new RecSample { Name = r.Next(0, 30), Value = r.Next(0, 30) });}// 先判断后入队PriorityQueue<RecSample, int> pq1 = new PriorityQueue<RecSample, int>();Stopwatch sw = Stopwatch.StartNew();for (int i = 0; i < 30000000; i++){foreach (var item in list){if (pq1.Count < 5)pq1.Enqueue(item, item.Value);else if (item.Value > pq1.Peek().Value)pq1.EnqueueDequeue(item, item.Value);}}sw.Stop();Console.WriteLine("先判断后入队耗时：" + sw.ElapsedMilliseconds);// 直接入队再出队PriorityQueue<RecSample, int> pq2 = new PriorityQueue<RecSample, int>();sw.Restart();for (int i = 0; i < 30000000; i++){foreach (var item in list){if (pq2.Count < 5)pq2.Enqueue(item, item.Value);elsepq2.EnqueueDequeue(item, item.Value);}}sw.Stop();Console.WriteLine("直接入队再出队耗时：" + sw.ElapsedMilliseconds);Console.ReadKey();}}

多次结果都是后者更优。看来是杞人忧天，不需要再去什么顶点判断，直接入队出队。

第二种：平常我们都是入队出队分成两步使用，比如queue<T>，出队Dequeue，入队Enqueue。现在PriorityQueue里面把两者结合合并，要么直接入队出队DequeueEnqueue,要会出队入队EnqueueDequeue。

现在简单测试分两步，与两步结合的情况：

    public struct RecSample{public int Name { get; set; }public int Value { get; set; }}//public class RecCompare : IComparer<RecSample>//{//    public int Compare(RecSample x, RecSample y)//    {//        return x.Value.CompareTo(y.Value);//    }//}internal class Program{private static void Main(string[] args){Random r = new Random();List<RecSample> list = new List<RecSample>();for (int i = 0; i < 30; i++){list.Add(new RecSample { Name = r.Next(0, 30), Value = r.Next(0, 30) });}// 先判断后入队PriorityQueue<RecSample, int> pq1 = new PriorityQueue<RecSample, int>();Stopwatch sw = Stopwatch.StartNew();for (int i = 0; i < 30000000; i++){foreach (var item in list){if (pq1.Count < 5){pq1.Enqueue(item, item.Value);}else{pq1.Enqueue(item, item.Value);pq1.Dequeue();}}}sw.Stop();Console.WriteLine("先判断后入队耗时：" + sw.ElapsedMilliseconds);// 直接入队再出队PriorityQueue<RecSample, int> pq2 = new PriorityQueue<RecSample, int>();sw.Restart();for (int i = 0; i < 30000000; i++){foreach (var item in list){if (pq2.Count < 5)pq2.Enqueue(item, item.Value);elsepq2.EnqueueDequeue(item, item.Value);}}sw.Stop();Console.WriteLine("直接入队再出队耗时：" + sw.ElapsedMilliseconds);Console.ReadKey();}}

结果是分两步还费时，结合效率更高。

下面截图就没有修改提示语了，自已结合代码看看吧。

结论：不用想当然，微软已经考虑了方方面面，所以直接使用吧，它既然有结合的，还有所考虑的，有时当傻瓜也是一种福气。