std::priority_queue<> 何时进行自我排序？

Question

我想知道C++ STL中的priority_queue是什么时候排序的。我的意思是，在使用push方法添加元素时，它是否会将元素插入到正确的位置，还是在peek或pop方法调用时自动排序并返回最高优先级的元素。我问这个问题是因为我的priority_queue中包含了数组索引，而数组可能会被更新，我希望当我调用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;
}

感谢您的选择。

- Richie Li

---

你可以轻松地发现这些属性，因为它像 map 一样需要一个比较谓词。如果你提供一个在每次比较时打印到控制台的比较谓词（例如），你将会实时看到它何时被调用（以及哪些值）。 - Matthieu M.

Answer 1

工作是在push()和pop()期间完成的，它们调用底层堆修改函数(push_heap()和pop_heap())。top()需要恒定时间。

- Kerrek SB

---

太棒了，这正是我想听到的。等时间限制结束后，我会将其标记为答案。 - Richie Li

这个链接的示例非常好地展示了行为。 - Doug T.

@StanleyCen：很高兴我能帮到你，不过我只是从some website上抄了一些信息... - Kerrek SB

哦，我一直以为priority_queue是一个顺序排序的容器。我猜堆要快得多。 - Mooing Duck

Answer 2

当插入新元素或删除现有元素时，它会自动排序。 这可能会有所帮助。

- Carl

Answer 3

std::priority_queue::push/(以及emplace)方法会在堆中引起高效的重新排序。

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

- makiolo