.NET 6中的PriorityQueue，表示具有值和优先级的集合

前言

我们常用Queue<T>类来表示先进先出(FIFO)集合，集合中的对象按照放入顺序检索。例如：

var jobs = new Queue<Job>();
 
jobs.Enqueue(new Job() { Id = 1 });
jobs.Enqueue(new Job() { Id = 2 });
jobs.Enqueue(new Job() { Id = 3 });
 
while (jobs.TryDequeue(out var job))
{
    Console.WriteLine(job.Id);
}
//输出
1
2
3

.PriorityQueue

在.NET 6中，新增了PriorityQueue<TElement,TPriority>类，可以用来表示具有值和优先级的集合。集合中的对象按照优先级值从小到大的顺序检索。

例如，最后放入队列的任务最紧急，需要有限处理：

var jobs = new PriorityQueue<Job, int>(); 

jobs.Enqueue(new Job() { Id = 1 }, 100);
jobs.Enqueue(new Job() { Id = 2 }, 100);
jobs.Enqueue(new Job() { Id = 3 }, 1);
 
while (jobs.TryDequeue(out var job,out var priority))
{
    Console.WriteLine(job.Id);
}

//输出
3
1
2

自定义比较器

优先级TPriority不必是数字，可以是任何类型，只要它的实例之间能比较大小。甚至，我们可以使用自定义比较器，实现复杂的优先级计算逻辑。

例如，我们按数字从大到小的顺序排列优先级：

var jobs = new PriorityQueue<Job, int>(); 

jobs.Enqueue(new Job() { Id = 1 }, 100);
jobs.Enqueue(new Job() { Id = 2 }, 200);
jobs.Enqueue(new Job() { Id = 3 }, 300);
 
while (jobs.TryDequeue(out var job,out var priority))
{
    Console.WriteLine(job.Id);
}

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

//输出
3
2
1

比较时机

那到底是放入队列时，还是从队列取出时进行比较呢？

我们用代码进行测试：

for (int i = 1; i <= 3; i++)
{
    Console.WriteLine($@"Enqueue {i}");
    jobs.Enqueue(new Job() { Id = i }, 100 * i);
}

for (int i = 4; i <= 6; i++)
{
    Console.WriteLine($@"Enqueue {i}");
    jobs.Enqueue(new Job() { Id = i }, -100 * i);
}
for (int i = 7; i <= 9; i++)
{
    Console.WriteLine($@"Enqueue {i}");
    jobs.Enqueue(new Job() { Id = i }, 100 * i);
}

Console.WriteLine("Dequeue");

while (jobs.TryDequeue(out var job,out var priority))
{
    Console.WriteLine(job.Id);
}

//输出
Enqueue 1
Enqueue 2
Compare(200, 100)
Enqueue 3
Compare(300, 200)
Enqueue 4
Compare(-400, 300)
Enqueue 5
Compare(-500, 300)
Enqueue 6
Compare(-600, 100)
Enqueue 7
Compare(700, 100)
Compare(700, 300)
Enqueue 8
Compare(800, 300)
Compare(800, 700)
Enqueue 9
Compare(900, 700)
Compare(900, 800)
Dequeue
Compare(200, 800)
Compare(-400, 800)
Compare(-500, 800)
Compare(700, 800)
Compare(100, -600)
Compare(300, 100)
Compare(700, 300)
9
Compare(200, 700)
Compare(-400, 700)
Compare(-500, 700)
Compare(300, 700)
Compare(100, -600)
Compare(300, 100)
8
Compare(200, 300)
Compare(-400, 300)
Compare(-500, 300)
Compare(100, 300)
Compare(100, -600)
7
Compare(200, 100)
Compare(-400, 200)
Compare(-500, 200)
Compare(-600, 200)
3
Compare(-600, 100)
Compare(-400, 100)
Compare(-500, 100)
2
Compare(-600, -500)
Compare(-400, -500)
1
Compare(-600, -500)
4
5
6

可以看到，放入和取出时都需要进行优先级比较。

放入时只和队列最顶部的元素进行比较，而取出时需要比较队列中所有剩余元素的优先级。

结论

通过上面的代码，可以发现PriorityQueue实际把队列中的元素分成了2堆：

Enqueue 8
Compare(800, 300)
Compare(800, 700)
Enqueue 9
Compare(900, 700)
Compare(900, 800)