Каково поведение std :: better в std :: priority_queue?
Когда я использовал std::greater<int> в качестве объекта функции сравнения в std::sort следующим образом:
std::sort(array_name, array_name + length, std::greater<int>());
Массив, отсортированный в порядке невозрастания (т.е. сначала наибольшее число)
Но когда я использовал ту же функцию сравнения в std::priority_queue, как показано ниже:
std::priority_queue <int, std::vector<int>, std::greater<int> > pq_name;
Почему функция-член std::priority_queue::top сначала возвращает наименьшее число?
(Мне нужно четкое сравнение двух случаев).
@codekaizer Хорошо, я сейчас читаю об этом, и мне кажется, что это полезный совет от вас, спасибо.
Ответы 2
CPPRef говорит об этом:
A user-provided Compare can be supplied to change the ordering, e.g. using std::greater would cause the smallest element to appear as the top().
Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by Compare.
Итак, для упорядочивания на основе std::less по умолчанию верхняя часть очереди - это самый большой элемент, который при сортировке идет последним. OTOH с std::greater последний элемент самый маленький.
На самом деле я прочитал это в той же ссылке перед тем, как спросить, но у меня до сих пор нет четкого сравнения между этими двумя случаями и почему std :: priority_queue ведет себя так? !!. Спасибо.
Хотя std :: priority_queue выводит сначала самые большие элементы, почему по умолчанию используется std :: less вместо std :: large (в отличие от первого случая в вопросе)?!
Чтобы понять, почему это происходит, вы должны понимать структуры данных, с которыми вы работаете.
Вопрос: Что такое массив?
А: Массив - это непрерывная область памяти, содержащая тип. Насколько нам известно, он может содержать любой тип объекта. Но поскольку вы работаете с int, в C++ целое число обычно состоит из 32 бит, но это зависит от обстоятельств. Следовательно, ваше представление в памяти будет примерно таким:
| 4 bytes | 4 bytes | 4 bytes | (...)
Когда вы сортируете массив, оператор std::greater<int> будет «сортировать» ваш массив, сохраняя большее целое число в первой позиции, второе по величине значение во второй позиции и так далее.
Вопрос: Что такое std::priority_queue?
А: Очередь с приоритетом - это куча, точнее, двоичное дерево. Куча - это структура данных, оптимизированная для возврата наибольшего значения по умолчанию. Этот тип кучи называется макс кучи. Но когда вы перегружаете сравнение в priority_queue с помощью оператора std::greater, вы преобразуете кучу в мин куча. Этот вид куч, аналогично тому, что происходит при перегрузке оператора метода std::sort, реализован для получения сначала минимального значения.
Имейте в виду, что представление кучи в памяти полностью отличается от представления в массиве.
Ваш способ объяснения очень прост и удивителен, спасибо.
возможно, будет понятнее, если вы сначала прочтете разницу между минимальной и максимальной кучей.