Когда std::priority_queue сортирует себя?

#c #algorithm #stl #computer-science #priority-queue

#c #алгоритм #stl #информатика #приоритет-очередь

Вопрос:

Мне было интересно, когда C STL priority_queue сортирует себя. Я имею insert в виду, попадает ли он в правильное место, когда вы push вводите элемент, или он сортируется сам по себе и дает вам элемент с наивысшим приоритетом, когда вы peek или pop он? Я спрашиваю об этом, потому что my priority_queue<int> будет содержать индекс массива, в котором могут обновляться значения, и я хочу, чтобы он обновлялся, когда я это делаю pq.top(); .

 #include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
  priority_queue<int> pq;
  pq.push(2);
  pq.push(5); //is the first element 5 now? or will it update again when I top() or pop() it out?
  return 0;
}

Спасибо.

1. Вы можете легко обнаружить эти свойства, потому что, как map и для этого требуется предикат сравнения. Если вы укажете предикат сравнения, который выводится на консоль (например) при каждом сравнении, вы увидите, когда он вызывается (и для каких значений).

Ответ №1:

Работа выполняется во push() время и pop() , которые вызывают базовые функции модификации кучи ( push_heap() и pop_heap() ). top() занимает постоянное время.

1. Потрясающе, это именно то, что я хотел услышать. Я отмечу это как ответ, как только истечет срок.

2. Приведенный здесь пример очень хорошо демонстрирует поведение

3. @StanleyGen: Рад, что смог помочь, хотя на самом деле я просто стащил информацию с какого-то веб-сайта …

4. О, я всегда думал, что priority_queue был последовательно отсортированным контейнером. Я думаю, что куча намного быстрее.

Ответ №2:

Он сортирует себя, когда вставляется новый элемент или удаляется существующий. Это может помочь.

Ответ №3:

метод std::priority_queue::push/(и emplace) вызывает эффективное изменение порядка в куче.

http://www.cplusplus.com/reference/queue/priority_queue/emplace/