使用 pair 创建 priority_queue，当第一个元素相等时，第一个元素的排序为“<”，第二个元素的排序为“>”

Question

我有一个基本的疑问，因为我正在尝试找出 C++ 中 priority_queue STL 的多功能性。

我知道默认情况下优先级队列实际上是max_heap。我也知道可以通过以下方式修改它以创建 min_heap:

priority_queue <int, vector<int>, greater<int> > pq;

我要实现的目标是，我想创建一个 priority_queue <pair <int,int> pq，这样堆对中的第一个元素是 max_heap，它是 min_heap 对中的第二个元素。例如，在插入以下对时：

(2,4) (1,5) (1,6)

显示元素时输出如下：

(2,4)
(1,5)
(1,6)

默认情况下，输出为：

(2,4)
(1,6)
(1,5)

可能吗？如果是，那又如何？

提前致谢。

Answer 1

您可以编写自定义比较，将第一个元素与 operator< 进行比较，将第二个元素与 operator> 进行比较。

struct less_then_greater {
    template<typename T, typename U>
    bool operator()(T const& lhs, U const& rhs) const {
        if (lhs.first < rhs.first) return true;
        if (rhs.first < lhs.first) return false;
        return lhs.second > lhs.second;
    }
};

std::priority_queue<std::pair<int, int>,
                    std::vector<std::pair<int, int>>,
                    less_then_greater
                   > pq;

请注意，这不是为一个创建最小堆，也不是为另一个创建最大堆。但根据您描述的输出，我认为这不是您真正要求的。

使用 pair 创建 priority_queue，当第一个元素相等时，第一个元素的排序为“<”，第二个元素的排序为“>”

Create priority_queue with pair such that sorting is "<" for first element and ">" for second element when 1st elements are equal

c++

priority-queue

std-pair