什么时候使用最大堆而不是最小堆？

Question

我最近刚接触堆，我看不出什么时候应该使用最大堆而不是最小堆，因为它（至少对我而言）与排序数组更相关。不过好像人气差不多？

什么时候设置最大堆比最小堆更有用？

Answer 1

例如，当您想首先处理优先级最低的事物时，您可以使用最小堆。当您想首先处理具有最高优先级数字的事物时，您可以使用最大堆。

例如，在很多情况下，"priority 1" 意味着这是最重要的事情。 "Priority 2" 项在 "priority 1" 项之后处理。您设置了一个最小堆，以便首先从堆中删除优先级较低的东西。

但在某些情况下，数字越大决定优先级。例如，您可能希望在处理 10 美元的订单之前处理 1000 美元的订单。在这种情况下，您设置了一个最大堆，以便首先处理价格较高的订单。

最大堆和最小堆之间的唯一区别是用于确定项目顺序的比较。一个使用 "less than,"，另一个使用 "greater than."

事实上，许多堆实现并不区分最小堆和最大堆。相反，它们让您传递一个进行排序的比较函数。所以如果你想从低到高排序，比较是这样的：

int compareForward(int x, int y)
{
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

如果你想从高到低排序，比较是这样的：

int compareReverse(int x, int y)
{
    if (x < y) return 1;
    if (x > y) return -11;
    return 0;
}

例如，参见 Java 的 PriorityQueue constructor that accepts a comparator parameter. Or the C++ standard library's std::priority_queue constructors，它也可以让您传递一个比较函数。

When to use max heap over min heap?