Может кто-нибудь объяснить, как std:: большее используется для реализации priority_queue

Question

std::priority_queue<int, vector<int>, std::greater<int> > pq;

---

Я не могу понять работу std:: большее в очереди приоритетов. Я заменяю minheap приоритетной очередью. этот код взят из geeksForGeeks реализации алгоритма Prims с использованием STL

Answer 1

std::priority_queue Тип - это то, что называется контейнерным адаптером. Он работает, начиная с типа, который можно использовать для представления последовательности, а затем использует этот тип для построения очереди с приоритетами (в частности, в виде двоичной кучи). По умолчанию используется вектор.

Для этого тип очереди с приоритетами должен знать, как сравнивать элементы друг с другом таким образом, чтобы определить, какие элементы "меньше", чем другие элементы. По умолчанию используется оператор меньше чем.

Если вы делаете стандарт std::priority_queue<int>, вы получите приоритетную очередь, которая

• использует std::vector для хранения и
• использует оператор меньше чем для сравнения элементов.

Во многих случаях это то, что вы хотите. Если вы вставите элементы в приоритетную очередь, созданную таким образом, вы будете читать их обратно от наибольших к наименьшим.

В некоторых случаях, однако, это не то поведение, которое вы хотите. Например, в алгоритме Прима и алгоритме Дейкстры вы хотите, чтобы значения возвращались в порядке возрастания, а не в порядке убывания. Чтобы сделать это, вам необходимо изменить порядок сравнений, используя оператор "больше" вместо "меньше".

Для этого вам нужно указать приоритетной очереди использовать другой метод сравнения. К сожалению, приоритетный тип очереди разработан таким образом, что если вы хотите это сделать, вам также необходимо указать, какой базовый контейнер вы хотите использовать. Я думаю, что это ошибка в дизайне - было бы очень просто иметь возможность указать компаратор, а не компаратор и контейнер - но c'est la vie. Синтаксис этого

std::priority_queue<int,               // store integers...
                    std::vector<int>,  // ... in a vector ...
                    std::greater<int>> // ... comparing using >