Блог

Пожалуйста, рассмотрите следующий код,

 using namespace std;
std::priority_queue<int,vector<int>,std::greater<int>> queue; //first

queue.push(26);
queue.push(12);
queue.push(22);
queue.push(25);

std::cout<<queue.top()<<endl;


std::priority_queue<int,vector<int>,std::less<int>> queue2; //second

queue2.push(26);
queue2.push(12);
queue2.push(22);
queue2.push(25);

std::cout<<queue2.top()<<endl;
  

Вывод:

12

26

В первом определении, которое я использовал, greater<int> все еще я получаю 12 (минимальное значение) в качестве выходных данных, в то время как при использовании less<int> я получаю 26 (максимальное значение).

Не следует greater<int> создавать максимальную кучу?

Что касается самого внутреннего алгоритма, std::priority_queue всегда создается «максимальная куча». Вам просто нужно научить его сравнивать элементы, чтобы он знал, что такое «max».

Чтобы определить порядок для этой «максимальной кучи», он использует предикат сравнения в стиле «меньше»: при задании пары (a, b) (в этом конкретном порядке) предикат должен указывать, a меньше или нет. b Использование информации о порядке, полученной из предиката, std::priority_queue гарантирует, что элемент greater находится в верхней части кучи. Standard std::less является примером такого предиката. Какой бы предикат вы ни предоставили, реализация будет рассматривать его как предикат в стиле «меньше».

Если вы укажете предикат, который реализует противоположное сравнение (например std::greater ), вы, естественно, получите минимальный элемент вверху. В принципе, можно сформулировать это так: std::priority_queue ожидается «меньший» предикат сравнения, и, предоставляя вместо этого «больший» предикат сравнения, вы, по сути, обманываете очередь (четко определенным образом). Основным следствием этого обмана является то, что для вас (внешнего наблюдателя) «максимальная куча» превращается в «минимальную кучу».

И это именно то, что вы наблюдаете.

Потому что это их работа. Предполагается, что less и greater моделируют операторы < и > соответственно и используются priority_queue для упорядочивания его элементов.

Они дают противоположные результаты, потому что они определены для этого (за исключением равных элементов).

Не следует greater<int> создавать максимальную кучу?

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

std::priority_queue — это «максимальная куча». Вы предоставляете оператор less-than; а элемент вверху является самым большим.

Во втором примере вы указали значение less-than, чтобы быть интуитивно понятным std::less; и вы видите самый большой элемент вверху.

В вашем первом примере вы считаете, что большее значение int «меньше» меньшего значения int; а «самый большой» элемент, основанный на вашем «меньше», на самом деле является наименьшим значением int.