c++ - std::priority_queue<> 什么时候进行 self 排序？

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() 需要常数时间。