具有自定义比较器的最小优先级队列

Question

我正在使用一个使用优先级队列的排序功能。该函数是模板化的，并采用自定义比较器：

template <class T, class Comparator>
void sort (std::vector<T>& myArray, Comparator comp) {}

该函数创建优先级队列：

std::priority_queue<T, std::vector<T>, Comparator > pQueue;

目前，top()和pop()返回并弹出最高值。

但是，我正在寻找一个最小优先级队列，当使用top()和pop()函数时返回并弹出最低值。我该怎么做呢？

Answer 1

std::priority_queue是一个最大堆（默认情况下），只有最大的元素可用。如果您希望它是一个小堆，那么您需要反转排序条件。所以，如果comp(a, b)如果true将返回a < b然后我们需要交换a和b将std::priority_queue变成一个小堆。那看起来像

template <class T, class Comparator>
void sort (std::vector<T>& myArray, Comparator comp)
{
    auto comp_reverse = [](const auto& lhs, const auto& rhs){ return comp(rhs, lhs); };
    std::priority_queue<T, std::vector<T>, decltype(comp_reverse)> pQueue;
    //...
}

Answer 2

只需交换给你的Comparator对象的参数：

auto cmp = [](auto a, auto b) { return Comparator()(b, a); };
std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);

---

请注意，您的Comparator（即Compare in std::priority_queue）必须提供严格的弱排序。

Compare类型提供严格的弱序。

但是，lambda表达式

auto cmp = [](auto a, auto b) { return !Comparator()(a, b); };

可能无法提供严格的弱序。例如，如果Comparator()(a, b)被定义为a < b，那么!Comparator()(a, b)将相当于!(a < b)，而a >= b相当于a > b并且与>明显不同。

与>=算子不同，a >= a算子是一个二元关系1，它不提供严格的弱排序，因为strictness2不成立，因为operator()确实是真的，即它实际上是反身的3。

---

（1）二元关系只是二元谓词，即带有两个参数的布尔函数，例如std::less<int>的关系运算符或<成员函数。

（2）二元关系，据说是严格的，如果它永远不适用于一个元素和它本身，例如a < a，因为<=永远不会成立。

（3）二元关系，如果它总是适用于一个元素本身，例如a <= a，它被认为是自反的，因为a < b总是成立。

Answer 3

将比较器包裹在交换参数顺序的东西中。

b > a与

template <typename Comparator>
struct invert
{
     template <typename Right, typename Left>
     bool operator()(Right&& rhs, Left&& lhs)
     { return comp(std::forward<Left>(lhs), std::forward<Right>(rhs)); }
     Comparator comp;
};

template <class T, class Comparator>
void sort (std::vector<T>& myArray, Comparator comp) 
{
    std::priority_queue<T, std::vector<T>, invert<Comparator> > pQueue(comp);
    // ...
}

完全相同。

qazxswpoi