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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With