为何自定义Comparer能让C# PriorityQueue实现大顶堆？

问题 #

我知道以下代码创建的是小顶堆：

var minHeap = new PriorityQueue<int, int>();

但为何使用如下Comparer创建的是大顶堆？

var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));

我查阅了Comparer文档，了解它接收Comparison委托，该委托用于判断两个元素的比较关系：y.CompareTo(x)在相等时返回0，y小于x时返回<0，y大于x时返回>0。我困惑的是这如何影响优先级队列的排序，是否返回值越大代表优先级越高？

解答 #

先明确.NET里PriorityQueue的核心规则：它的比较器是用来判断两个元素谁的优先级更高、应该排在前面，具体逻辑是：

• 当Compare(x, y)返回负数时：x的优先级高于y，x会被排在y前面（先出队）
• 当返回正数时：y的优先级高于x，y会被排在x前面（先出队）
• 返回0时：两者优先级相同，顺序不做强制要求

默认的小顶堆用的是Comparer<int>.Default，对应的比较逻辑是(x, y) => x.CompareTo(y)：
比如x=2，y=5时，x.CompareTo(y)返回负数，所以x优先级更高，先出队——这就实现了小的数先被取出，也就是小顶堆。

再看你写的比较器(x, y) => y.CompareTo(x)，我们拆解两种典型情况：

1. 当x=2，y=5时：y.CompareTo(x)返回正数（5比2大，返回1），根据规则，y的优先级更高，会排在x前面，也就是大的数先出队
2. 当x=5，y=2时：y.CompareTo(x)返回负数（2比5小，返回-1），根据规则，x的优先级更高，排在y前面，还是大的数在前面

这种反转的比较逻辑，直接把优先级判断的规则倒了过来，自然就从默认的小顶堆变成了大顶堆。

对你的疑问做个明确回答：不是返回值越大优先级越高，核心是返回值的正负决定了两个元素的相对优先级——返回负数代表第一个参数优先级高，返回正数代表第二个参数优先级高。

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