компараторы в функции сортировки и очереди приоритетов С++

В функции C++ Sort третий необязательный параметр — это компаратор, используемый для сортировки объектов. Если мы передадим в качестве компаратора less, мы получим объекты в возрастающем порядке. (если компаратор оценивается как истинный, позиции не будут изменены, иначе элементы будут заменены местами!) Правильно ли я понимаю?

Таким же образом, если мы передаем компаратор less в очередь с приоритетом, мы должны получить минимальную кучу (если в качестве базовой структуры данных выбрана векторная, объекты сортируются в порядке возрастания. Если мы вызываем top(), то будет возвращен первый элемент вектора, который является наименьшим числом.Поэтому я думаю, что это минимальная куча) почему мы получаем максимальную кучу?


c++ comparator priority-queue min-heap max-heap
person Zixin Liu    schedule 04.07.2018    source источник
comment
Первая часть вашего утверждения верна. Однако, чтобы получить минимальную кучу, вам нужно передать std::greater, иначе по умолчанию std::less создает поведение максимальной кучи. Это указано в документации.   -  person Cory Kramer    schedule 04.07.2018
comment
Обратите внимание, что предположение о том, что возврат true оставляет порядок неизменным, неверно. Два элемента не обязательно должны передаваться в том же порядке, в котором они появляются в исходном векторе.   -  person Raymond Chen    schedule 04.07.2018
comment
std::priority_queue по умолчанию просто максимальная куча. На самом деле больше нечего объяснять.   -  person BessieTheCookie    schedule 05.07.2018

Ответы (1)


arrow_upward
1
arrow_downward

Согласно этой онлайн-документации, класс std::priority_queue библиотеки C++ возвращает самый большой элемент сначала в том смысле, что компаратор упорядочивает меньшие элементы перед более крупными элементами. Из ссылки выше:

Обратите внимание, что параметр Compare определен таким образом, что он возвращает true, если его первый аргумент стоит перед вторым аргументом в слабом порядке. Но поскольку очередь с приоритетом сначала выводит самые большие элементы, элементы, которые «предшествуют», фактически выводятся последними. То есть начало очереди содержит «последний» элемент в соответствии со слабым порядком, установленным Compare.

Таким образом, std::priority_queue<T,std::less<T>> создает максимальную кучу и отдает приоритет более крупным элементам.

person Walter    schedule 04.07.2018