任何人都可以解释一下如何在 C# 中创建最大堆吗？

Question

我知道这是一个最小堆

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

但是为什么这个比较器会产生最大堆？

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

我尝试查看 Comparer 的文档，发现它需要一个 Comparison 委托。委托确定两个元素如何相互比较。如果相等，y.CompareTo(x) 将返回 0；如果 y 大于 x，则返回 <0 if y is less than x and >0。我感到困惑的是这如何影响优先级队列中的排序。是因为较大的比较值（例如 y.CompareTo(x) 返回较大的值）会导致较高的优先级吗？

Answer 1

想象一下您正在构建一个二进制堆。您插入第一个项目 1，然后插入第二个项目 2。如果它是最小堆，则 2 应该成为左孩子。如果它是最大堆，则 2 成为新根，1 成为左孩子。

所以，让我们看看：

minheap_insert(heap, y)
    // min heap
    x = heap.PeekMin();  // get the heap root
    if (x.CompareTo(y) > 0)
    {
        // heap root is larger than the new item
        // Make the new item the root of the heap
    }

maxheap_insert(heap, y)
    // max heap
    x = heap.PeekMin(); // get the heap root
    if (y.CompareTo(x) > 0)
    {
        // new item is larger than the heap root
        // Make the new item the root of the heap
    }