.NET 6 中的 PriorityQueue

Intro

.NET 6 中引入了一个新的集合类型 PriorityQueue，正如它的名字那样，在普通的 Queue 基础之上增加了优先级的支持，接下来就一起来看一下怎么使用，以及一些常用的使用场景介绍。

Get Started

来看一个简单的使用示例：

var priorityQueue = new PriorityQueue<string, int>();  
priorityQueue.Enqueue("Alice", 100);  
priorityQueue.EnqueueRange(Enumerable.Range(1, 5)  
    .Select(x => ($"X_{x}", 100 - x))  
);  
  
while (priorityQueue.TryDequeue(out var element, out var priority))  
{  
    Console.WriteLine($"Element:{element}, {priority}");  
}  

输出示例：

可以看到输出的顺序和我们添加的顺序是相反的， PriorityQueue 在 Dequeue 的时候是从优先级最小开始的，值越小优先级越高，优先级越高越优先输出，如果我们希望最大先输出是不是可以呢，答案是肯定的，只是我们需要指定我们自己的优先级比较规则就可以了，可以参考后面的示例

Scenes

借助带优先级的自动排序，我们可以做一些自动排序的需求的时候可以考虑使用 PriorityQueue

Message Queue

借助 PriorityQueue 可以来实现一个优先级消息队列，允许用户在发消息的时候指定一个消息的优先级，在消费的时候就会按优先级

var random = new Random();  
  
var queue = new PriorityQueue<string, int>();  
for (var i = 1; i <= 10; i++)  
{  
    queue.Enqueue($"Message_{i}", random.Next(10, 100));  
}  
  
while (queue.TryDequeue(out var message, out _))  
{  
    Console.WriteLine(message);  
}  

在上面的示例里我们默认指定了一个 int 作为 Priority 的类型，并入队了一些消息，但是往往会有很多的消息，可能会出现优先级相同的情况，我们可以使用时间和int 作为一个联合的 Priority 类型，可以参考下面的示例：

var random = new Random();  
  
var queue = new PriorityQueue<string, (DateTime time, int priority)>(new DateTimePriorityComparer());  
  
var time = DateTime.UtcNow;  
Thread.Sleep(1000);  
for (var k = 0; k < 3; k++)  
{  
    for (var i = 1; i <= 3; i++)  
    {  
        queue.Enqueue($"Message_{i}_{k}", (i > 2 ? time : DateTime.UtcNow, random.Next(5, 10)));  
    }  
}  
  
while (queue.TryDequeue(out var message, out var priority))  
{  
    Console.WriteLine($"{message}, {priority.priority}, {priority.time}");  
}  

输出示例如下：

internal class DateTimePriorityComparer : IComparer<(DateTime time, int priority)>  
{  
    public int Compare((DateTime time, int priority) x, (DateTime time, int priority) y)  
    {  
        var priorityComparison = x.priority.CompareTo(y.priority);  
        if (priorityComparison != 0) return priorityComparison;  
        return x.time.CompareTo(y.time);  
    }  
}  

Rank

在很多做排行榜的应用中也可以使用 PriorityQueue 来实现，比如我们来做一个学生成绩的排名来看下面的示例代码：

var list = new List<(string name, int score)>  
{  
    ("Mike", 99),  
    ("Ming", 100),  
    ("Jane", 96),  
    ("Yi", 94),  
    ("Harry", 90),  
};  
  
var priorityQueue = new PriorityQueue<string, int>();  
priorityQueue.EnqueueRange(list);  
  
Console.WriteLine("--Unordered:");  
foreach (var item in priorityQueue.UnorderedItems)  
{  
    Console.WriteLine($"Name:{item.Element}, score:{item.Priority}");  
}  
  
Console.WriteLine("--Ordered:");  
while (priorityQueue.TryDequeue(out var name, out var score))  
{  
    Console.WriteLine($"Name:{name}, score:{score}");  
}  
  
Console.WriteLine("-----TOP 3");  
priorityQueue = new PriorityQueue<string, int>(new High2LowComparer());  
priorityQueue.EnqueueRange(list);  
var rank = 0;  
while (rank++ < 3 && priorityQueue.TryDequeue(out var name, out var score))  
{  
    Console.WriteLine($"Rank({rank}):Name:{name}, score:{score}");  
}  

上面的 list 就是一个成绩清单，随便写了几个测试数据，通过 PriorityQueue 的 UnorderedItems 我们可以拿到排序之前的数据，也是我们加入队列(Enqueue)的顺序，默认的比较是小的在前，也就是成绩低的在前，那我们想按从大到小排序的话就需要自定义比较方式。上面的 High2LowComparer 就是一个自定义的比较，其实就是把比较的结果取了一个反，代码如下：

internal class High2LowComparer : IComparer<int>  
{  
    public int Compare(int x, int y)  
    {  
        return y.CompareTo(x);  
    }  
}  

上面的输出结果如下：

More

Redis 里有一个 zset(sortedSet) 类型的数据也可以做类似的事情，但是 zset 和 PriorityQueue 还是有一些不同的，zset 是一个 set，是一个自动去重的集合，而 PriorityQueue 还是一个 Queue 不会去重，zset 可以修改对应元素的 priority（score)，但是 PriorityQueue 目前不支持修改元素对应的优先级PriorityQueue  可以解决我们的一些问题，但是有一些使用要注意的地方：

1. 首先如果 Priority 是一样的话，输出的顺序是有可能不一样的，这是由它内部的实现算法决定的，不能严格的保证顺序
2. PriorityQueue 是非线程安全的，需要注意线程安全问题
3. PriorityQueue 中的 Peek 方法只会获取 queue 里即将出队的元素，但是不会从队列中移除这个元素

- EOF -

推荐阅读  点击标题可跳转

看完本文有收获？请转发分享给更多人

推荐关注「DotNet」，提升.Net技能 

点赞和在看就是最大的支持❤️