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

Question

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

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

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

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

Answer 1

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

1. std::priority_queue контейнерный адаптер; основные соображения памяти делают спину предпочтительным местом для изменений (с pop_back() а также push_back()) для контейнеров последовательности, таких как std::vector,
2. priority_queue примитивы основаны на std::make_heap (конструктор), std::pop_heap + container::pop_back (priority_queue::pop) и на container::push_back + std::push_heap (priority_queue::push)
3. pop_heap возьмет переднюю часть основного хранилища и поместит его сзади, впоследствии восстановив инвариант кучи. Обратное идет для push_heap,
4. дела sort_heap на max_heap (с максимальным на передней части изначально) будет многократно выталкивать фронт на заднюю часть и сортировать диапазон в соответствии с less (который является оператором сравнения по умолчанию)
5. следовательно, предпочтительная реализация max_heap должен иметь максимальный элемент по отношению к less на передней панели, доступ через priority_queue::top (лежащие в основе container::front).
6. все еще можно спорить, интуитивно ли это priority_queue с std::less компаратор представляет собой max_heap, Это можно было бы определить как min_heap путем изменения аргументов компаратора (но см. комментарий @TC о том, что для связывателей C++98 это довольно многословно) везде при вызовах различных функций кучи. Единственным (для меня) нелогичным результатом было бы top() тогда бы не дал элемент с высшим приоритетом

Answer 2

Функции кучи 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 нужна максимальная куча.

Answer 3

Это процесс, который преобразует приоритетную очередь в отсортированную последовательность.

Как мы можем этого добиться?

Предположим, что теперь у нас есть максимальная куча, мы выполним следующую процедуру.

      HEAP-SORT(A)
    for i = A.heap_size downto 2
        exchange A[1] with A[A.heap_size]
        A.heapsize -= 1
        max_heapify(A)

Когда мы закончим эту процедуру, мы получим последовательность возрастающего порядка.

Мы замечаем, что каждый раз, когда мы сравниваем два элемента, мы всегда помещаем больший элемент обратно в массив, что означает, что меньший элемент находится слева от большего.

И это соответствует идее, когда мы передаем оператор less в алгоритм std::sort для получения последовательности возрастающего порядка.

Answer 4

A — это структура данных, в которой элементы хранятся таким образом, что элемент с наивысшим приоритетом всегда находится в начале очереди. По умолчанию приоритет элемента определяется его значением. Однако вы можете использовать функтор, чтобы изменить способ определения приоритета элемента.

Функтор — это небольшой функциональный объект, который можно использовать для выполнения определенной задачи. В этом случае функтор используется для сравнения двух целых чисел и возврата значения true, если первое целое число больше второго.

Когда вы используете функтор с, элемент с наименьшим значением будет считаться имеющим наивысший приоритет. Это потому, чтоФунктор всегда будет возвращать true при сравнении элемента с наименьшим значением с любым другим элементом.

Answer 5

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