.NET 9 Preview 1 PriorityQueue 更新

Intro

.NET 6 开始内置了一个 PriorityQueue，之前有写过一篇介绍文章，可以参考：.NET6 中的 PriorityQueue

.NET 9 新增了 Remove 方法来移除 queue 里的某一个元素

Sample

新增 API 定义如下：

public bool Remove(TElement element, out TElement removedElement, out TPriority priority, IEqualityComparer<TElement>? equalityComparer = null);

我们可以通过 Remove 方法的返回值来判断是否移除成功

var queue = new PriorityQueue<string, int>();

queue.Enqueue("Lily", 88);
queue.Enqueue("Ming", 80);
queue.Enqueue("Alice", 90);
queue.Enqueue("Mike", 85);
queue.Enqueue("Amy", 99);
queue.Enqueue("Alex", 98);

if (!queue.Remove("Jane", out _, out _))
{
    Console.WriteLine("Jane not existed");
}

if (queue.Remove("Alice", out _, out _))
{
    Console.WriteLine("Alice removed");
}

Remove 的时候可以提供一个自定义的相等性比较，所以我们也可以使用自定义的比较器来 override 默认的，例如：

if (!queue.Remove("mike", out _, out _))
{
    Console.WriteLine($"mike not exists");
}

if (queue.Remove("mike", out var removedElement, out var removedPriority, StringComparer.OrdinalIgnoreCase))
{
    Console.WriteLine($"RemovedElement - {removedElement}: {removedPriority}");
}

借助于此我们也可以变相地实现 Update 的功能

if (queue.Remove("alex", out removedElement, out removedPriority, StringComparer.OrdinalIgnoreCase))
{
    queue.Enqueue(removedElement, 60);
    Console.WriteLine($"Element priority updated: {removedElement}, previous priority: {removedPriority}, new priority: {60}");
}

使用得比较多可以封装一个扩展方法

public static void EnqueueOrUpdate<TElement, TPriority>(this PriorityQueue<TElement, TPriority> queue, TElement element, TPriority priority)
{
    queue.Remove(element, out _, out _);
    queue.Enqueue(element, priority);
}

完整的示例如下：

var queue = new PriorityQueue<string, int>();

queue.Enqueue("Lily", 88);
queue.Enqueue("Ming", 80);
queue.Enqueue("Alice", 90);
queue.Enqueue("Mike", 85);
queue.Enqueue("Amy", 99);
queue.Enqueue("Alex", 98);

if (!queue.Remove("Jane", out _, out _))
{
    Console.WriteLine("Jane not existed");
}        
if (queue.Remove("Alice", out _, out _))
{
    Console.WriteLine("Alice removed");
}        

Console.WriteLine();
// remove with custom equality comparer
if (!queue.Remove("mike", out _, out _))
{
    Console.WriteLine($"mike not exists");
}
if (queue.Remove("mike", out var removedElement, out var removedPriority, StringComparer.OrdinalIgnoreCase))
{
    Console.WriteLine($"RemovedElement - {removedElement}: {removedPriority}");
}

// update priority
if (queue.Remove("alex", out removedElement, out removedPriority, StringComparer.OrdinalIgnoreCase))
{
    queue.Enqueue(removedElement, 60);
    Console.WriteLine($"Element priority updated: {removedElement}, previous priority: {removedPriority}, new priority: {60}");
}

Console.WriteLine();
Console.WriteLine("PriorityQueue elements:");
while (queue.TryDequeue(out var element, out var priority))
{
    Console.WriteLine($"{element}: {priority}");
}

Console.WriteLine();

输出结果如下

More

目前还没 UpdatePriority 之类的方法，如果你需要也可以在这个 issue 上进行反馈

https://github.com/dotnet/runtime/issues/44871

基于 Remove 方法，PR 还提供了一个简单的 Dijkstra 最短路径算法的示例，有需要可以查看 https://github.com/dotnet/runtime/pull/93994/files#diff-4af9482a6250d6c44d2ee4c349fa4c3f97b977e4980e8cdb594ab8c481e9e352R18

References

• https://github.com/dotnet/runtime/issues/44871
• https://github.com/dotnet/runtime/issues/93925
• https://github.com/dotnet/runtime/pull/93994
• https://github.com/WeihanLi/SamplesInPractice/blob/main/net9sample/Net9Samples/PriorityQueueSample.cs
• https://www.freecodecamp.org/chinese/news/dijkstras-shortest-path-algorithm-visual-introduction/
• .NET6 中的 PriorityQueue