очередь приоритета stl, основанная сначала на более низком значении

Question

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

А какова сложность построения очереди приоритетов stl. Если я использую быструю сортировку в массиве, который принимает O (nlgn), то его сложность аналогична использованию очереди приоритетов ???

Пожалуйста, кто-то.

Answer 1

1. priority_queue имеет параметры шаблона, которые определяют тип контейнера и сравнение для использования при заказе. По умолчанию сравнение составляет less<T>; чтобы получить обратный порядок, используйте priority_queue<T, vector<T>, greater<T>>.

2. Вставка в очередь с приоритетами занимает логарифмическое время, поэтому построение очереди из N элементов имеет сложность O(N logN), то же самое, что построение и сортировка вектора. Но как только он построен, вставка в очередь приоритетов остается логарифмической, тогда как вставка в отсортированный вектор является линейной.

Answer 2

Используйте тип

priority_queue<T, vector<T>, greater<T> >

Answer 3

Вы можете просто нажать значения, умножив их на -1, чтобы они были сохранены в обратном порядке, в отличие от фактического порядка по умолчанию ... и снова умножить значение на -1 при извлечении данных, чтобы получить их в фактическом виде. *

Answer 4

Используйте другой компаратор в качестве 3-го аргумента шаблона std::priority_queue.

priority_queue - это контейнерный адаптер, который работает с любой определенной вами последовательностью. Производительность вставки равна операции std::push_heap и занимает логарифмическое время. Таким образом, сложность сортировки после всех вставок не одинакова. Если вы вставите фиксированную сумму и обработаете очередь впоследствии, vector и один sort могут быть более эффективными.

Answer 5

Заменить T ниже с переменным типом.Вы получите свою работу

priority_queue<T, vector<T>, greater<T> > PQ;

Например, для переменной типа int вы можете написать ее так:

priority_queue<int, vector<int>, greater<int> > Q;