优先级队列未正确比较 C++

Question

我正在尝试创建一个由 int、char 对组成的优先级队列，它为我提供具有更大 int 的对，但我的代码无法正常工作。我做错了什么？

这是我的比较器class:

class Compare
{
public:
    bool operator() (pair<int, char>a, pair<int, char>b)
    {
        return a.first > b.first;
    }
};

这是我的优先队列：

priority_queue<pair<int, char>, vector<pair<int, char>>, Compare> party;

但是如果我执行代码：

party.push(make_pair(2, 'A'));
party.push(make_pair(3, 'B'));
cout<<party.top().first;

它 returns 2，而不是 3。我该如何修复优先级队列的实现？

Answer 1

Geordi La Forge 将使用的相同修复方法：反转极性：

bool operator() (const pair<int, char> &a, const pair<int, char> &b) const
{
    return a.first < b.first;
}

比较函数始终执行严格的弱排序，a.k.a。逻辑 < 操作。但是priority_queue，根据定义，gives you the largest value in the priority queue, first:

... provides constant time lookup of the largest (by default) element,

但是比较函数仍然是严格的弱排序：

A Compare type providing a strict weak ordering.

有点反直觉，但过了一会儿，它确实有道理...

P.S.：比较函数应该是一个const函数，并且带const个参数，为了效率，如我的例子所示；但这是一个额外的细节。

Answer 2

优先级队列期望 Comparator 实现 less - 与任何其他需要弱排序的容器一样。但是，它的工作原理是将较大的元素放在顶部。由于您有效地实施了 greater，因此您颠倒了队列，现在最小的元素排在最前面。

要解决此问题，请将比较器更改为两个元素中的 return 较小者。

Priority Queue Not Comparing Correctly C++