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

Question

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

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

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

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

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

13

c++c++11 heap min-heap priority-queue

Решение

Другие решения

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

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

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

8

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

0

Источник

Accepted Answer

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

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 (с максимумом спереди изначально) будет неоднократно совать спереди назад и сортировать диапазон в соответствии с less (который является оператором сравнения по умолчанию)
следовательно, предпочтительная реализация max_heap должен иметь максимальный элемент w.r.t. less на передней панели, доступ через priority_queue::top (лежащие в основе container::front).
все еще можно спорить, интуитивно ли это priority_queue с std::less компаратор представляет собой max_heap, Это можно было бы определить как min_heap путем изменения аргументов компаратора (но см. комментарий @ T.C. о том, что для связывателей C ++ 98 это довольно многословно) везде в вызовах различных функций кучи. Единственным (для меня) нелогичным результатом было бы top() тогда бы не дал элемент с Топ приоритет

6