Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

When does a std::priority_queue<> sort itself?

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.

like image 758
Richie Li Avatar asked Oct 18 '11 01:10

Richie Li


1 Answers

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

like image 157
Kerrek SB Avatar answered Oct 24 '22 20:10

Kerrek SB