CODEWITHSUNDEEP
c++algorithmstlcomputer-sciencepriority-queue
Richie Li
Richie Li

Reputation: 1267

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.

Upvotes: 5

Views: 3061

Answers (3)

makiolo
makiolo

Reputation: 176

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

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

Upvotes: 0

Carl
Carl

Reputation: 44448

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

Upvotes: 1

Kerrek SB
Kerrek SB

Reputation: 477040

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

Upvotes: 10

Related Questions