.NET6 中的 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 里即将出队的元素，但是不会从队列中移除这个元素

References

• https://devblogs.microsoft.com/dotnet/announcing-net-6-preview-2/

• https://github.com/dotnet/runtime/blob/v6.0.0-preview.2.21154.6/src/libraries/System.Collections/src/System/Collections/Generic/PriorityQueue.cs

• https://github.com/WeihanLi/SamplesInPractice/blob/master/net6sample/PriorityQueueSample/Program.cs