C#中使用PriorityQueue创建最大堆时遇类型转换错误求助

错误根源 #

你使用的PriorityQueue<Pair, int>是元素类型为Pair，优先级类型为int的队列，它的构造器接受的比较器是用来比较int类型的优先级值的，但你传入的是Comparer<Pair>（用于比较Pair对象），类型完全不匹配，这就是编译报错的直接原因。

两种解决方式 #

方式1：利用负优先级实现最大堆（通用所有.NET版本）

PriorityQueue默认是最小堆，要实现按freq降序的最大堆，可以将优先级设为freq的负值，让原本最大的freq对应最小的负数值，被优先取出：

var pq = new PriorityQueue<Pair, int>();
// 入队时传入负的freq作为优先级
pq.Enqueue(new Pair(5, 2), -5);
pq.Enqueue(new Pair(3, 1), -3);
// 取出时会先拿到freq=5的Pair
var top = pq.Dequeue();

方式2：直接比较Pair对象（.NET 8及以上版本支持）

.NET 8新增了无需指定优先级类型的PriorityQueue<TElement>，可以直接传入Pair的比较器：

// 直接传入Pair的比较器，按freq降序排序
var pq = new PriorityQueue<Pair>(Comparer<Pair>.Create((x, y) => y.freq.CompareTo(x.freq)));
pq.Enqueue(new Pair(5, 2));
pq.Enqueue(new Pair(3, 1));

方式3：指定优先级比较器（低于.NET 8版本）

如果用的是低于.NET 8的版本，可以传入int类型的降序比较器，同时将freq作为优先级值：

// 创建int类型的降序比较器
var intDescComparer = Comparer<int>.Create((a, b) => b.CompareTo(a));
var pq = new PriorityQueue<Pair, int>(intDescComparer);
// 入队时传入freq作为优先级
pq.Enqueue(new Pair(5, 2), 5);
pq.Enqueue(new Pair(3, 1), 3);

内容的提问来源于stack exchange，提问作者codingBeast