|
priority_queue is a binary heap (as I said, it's just a wrapper around the standard heap functions). Push and pop are O(log N). They do not have to 're-sort' the list, only perform updates to maintain the heap invariant. Basically what happens is the new item is added to the end of the vector (amortized constant time), and is then pushed up the tree. Since a binary heap is a complete binary tree (each level is completely filled from left to right), the tree never has more than log2 N levels, and this is efficient.
Normally I would agree to wait and see if it's a performance issue, but it's such a straightforward and easy optimization...
|