Минимальная приоритетная очередь с пользовательским компаратором

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

Заверните компаратор во что-то, меняющее порядок параметров.

a < b точно равно 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);
    // ...
}

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 вstd::priority_queue) должен обеспечивать строгий слабый порядок .

A Compare тип, обеспечивающий строгий слабый порядок.

Однако,лямбда-выражение

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) двоичное отношение - это просто двоичный предикат , т. Е. Булева функция, принимающая два параметра, например, реляционные операторы или operator() функция-член std::less<int>.}

^{(2) Бинарное отношение, которое называется строгим , если оно никогда не содержит для элемента и самого себя, например, <, поскольку a < a никогда не выполняется.}

^{(3) Бинарное отношение, которое называется возвратным , если оно всегда выполняется для элемента исам, например, <=, поскольку a <= a всегда выполняется.}

Answer 3

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;
    //...
}