Причина использования `std:: greater` для создания минимальной кучи через` priority_queue`

Мне интересно, почему для создания кучи min с помощью priority_queue следует использовать std::greater?

std::priority_queue<T, std::vector<T>, std::greater<T> > min_heap;

Для меня, поскольку наименьшее значение всегда находится в верхней части кучи, используемый класс должен быть std::less

Update: С другой стороны, поскольку поведение по умолчанию priority_queue (max heap) заключается в том, чтобы удерживать наибольшее значение вверху, мне кажется, что std::greater следует использовать для создания максимальной кучи, а не для создания минимальной кучи

Ответы

Ответ 1

Логический аргумент выглядит следующим образом

  • std::priority_queue - контейнерный адаптер; основные соображения памяти делают заднюю часть предпочтительным местом для модификаций (с pop_back() и push_back()) для контейнеров последовательностей, таких как std::vector.
  • примитивы priority_queue основаны на std::make_heap (конструктор), std::pop_heap + container::pop_back (priority_queue::pop) и на container::push_back + std::push_heap (priority_queue::push)
  • pop_heap возьмет перед собой базовое хранилище и положит его обратно, после чего восстановит инвариант кучи. Обратное идет для push_heap.
  • Выполняя sort_heap на max_heap (сначала с max на фронте), снова выворачивает фронт назад > и сортирует диапазон в соответствии с less (который является оператором сравнения по умолчанию)
  • следовательно, предпочтительная реализация max_heap состоит в том, чтобы иметь максимальный элемент w.r.t. less спереди, доступ через priority_queue::top (ниже container::front).
  • можно по-прежнему обсуждать, является ли интуитивно понятным, что priority_queue с компаратором std::less представляет a max_heap. Его можно было бы определить как min_heap, изменив аргументы компаратора (но см. Комментарий от @T.C., Что с связями С++ 98 это довольно многословно) во всех случаях в вызовах различных функций кучи. Один (для меня) контр-интуитивный результат состоял бы в том, что top() не предоставил бы элемент с наивысшим приоритетом

Ответ 2

Функции кучи С++ make_heap, push_heap и pop_heap работают на max heap, то есть верхний элемент - это максимум при использовании компаратора по умолчанию. Итак, чтобы создать мини-кучу, вам нужно использовать greater<T> вместо less<T>.

Я подозреваю, что вместо кучи минимальной кучи используется максимальная куча, что ее легче реализовать с помощью операции less. В С++ less имеет специальную привилегию быть сортированным компаратором по умолчанию для всех алгоритмов STL; если вы собираетесь реализовать только одну операцию сравнения (кроме ==), она должна быть <. Это приводит к неудачной причуде, что priority_queue<T, C<T>, less<T>> означает max-queue, а priority_queue<T, C<T>, greater<T>> означает min-queue.

Кроме того, для некоторых алгоритмов, таких как nth_element, требуется максимальная куча.

Ответ 3

См. http://en.cppreference.com/w/cpp/container/priority_queue. A priority_queue предназначен для размещения наибольшего значения в верхней части. Это происходит, если вы используете компаратор по умолчанию std::less. Поэтому, если вам нужно обратное поведение, вам нужно использовать обратный компаратор, std::greater.