问题描述:

I was wondering when the C++ STL priority_queue sorts itself. I mean does it insert it into a correct place when you push the item in, or does it sort itself and give you the item of highest priority when you peek or pop it out? I'm asking this because my priority_queue<int> will contain an index to an array that may have values update, and I want it to update when I do 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;

}

Thanks.

网友答案:

The work is done during push() and pop(), which call the underlying heap modification functions (push_heap() and pop_heap()). top() takes constant time.

网友答案:

It sorts itself when a new element is inserted or an existing one is removed. This might help.

网友答案:

std::priority_queue::push/(and emplace) method causes a efficient reorder in heap.

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

相关阅读:
Top