компараторы в функции сортировки и очереди приоритетов Переполнение стека
В функции сортировки C ++ третьим необязательным параметром является компаратор, используемый для сортировки объектов. Если мы передадим меньше в качестве компаратора, мы получим объекты в возрастающем порядке. (если компаратор оценен как истинный, позиции не будут изменены, иначе элементы будут поменяны местами!) Правильно ли мое понимание?
Аналогичным образом, если мы передадим меньший компаратор в приоритетную очередь, мы должны получить минимальную кучу (если базовая структура данных выбрана векторной, объекты сортируются в порядке возрастания. Если мы вызываем top (), будет возвращен первый элемент вектора, который является наименьшим числом, поэтому я думаю, что это минимальная куча) почему мы получаем максимальную кучу?
Решение
В соответствии с эта онлайн документация, класс библиотеки C ++ std::priority_queue возвращает крупнейший Элемент сначала в том смысле, что компаратор упорядочивает меньшие элементы перед более крупными. Сверху ссылка:
Обратите внимание, что параметр Compare определен так, что он возвращает true
если его первый аргумент предшествует второму аргументу в слабом
упорядоченность. Но поскольку приоритетная очередь выводит самые большие элементы
во-первых, элементы, которые «предшествуют», на самом деле выводятся последними. Тот
передний конец очереди содержит «последний» элемент согласно
слабое упорядочение, налагаемое сравнением.
таким образом std::priority_queue<T,std::less<T>> создает максимальную кучу и расставляет приоритеты для больших элементов.
Другие решения
Других решений пока нет …