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

Question

Мне было интересно, когда C ++ STL priority_queue сортируется сам. Я имею в виду, делает ли это insert правильное место, когда вы push входите в предмет, или же оно само сортируется и дает вам предмет наивысшего приоритета, когда вы peek или pop выводите его? Я спрашиваю об этом, потому что мой 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;
}

Спасибо.

Answer 1

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

Answer 2

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

Answer 3

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

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