什么时候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()需要不断的时间.