问题描述
我有一个应用程序（C ++），我认为很好地服务于STL priority_queue 。 说：
I have an application (C++) that I think would be well served by an STL priority_queue. The documentation says:
Priority_queue是一个容器适配器，这意味着它是在一些底层容器类型之上实现的。默认情况下，底层类型是向量，但可以明确选择不同的类型。
和
我以前假定 top（） / code>是 O（1），而 push（）将是一个 O（logn）（我首先选择了 priority_queue 的两个原因） - 但是文档既不确认也不否认这一假设。
I had previously assumed that top() is O(1), and that push() would be a O(logn) (the two reasons I chose the priority_queue in the first place) - but the documentation neither confirms nor denies this assumption.
深入挖掘Sequence序列的文档说：
Digging deeper, the docs for the Sequence concept say:
priority_queue 一个矢量（默认情况下）作为堆，其中：
The priority_queue uses a vector (by default) as a heap, which:
我推断，使用默认的 priority_queue ， top（）是 O（1）和 push（）是 O（n）。
I'm inferring that, using the default priority_queue, top() is O(1) and push() is O(n).
问题1：这是否正确？ （ top（）访问是 O（1）和 push（）是 O（n）？）
Question 1: Is this correct? (top() access is O(1) and push() is O(n)?)
问题2：如果我使用集合，可以实现（或 O（logn）效率 push（） multiset ），而不是矢量用于执行 priority_queue ？这样做会有什么后果？还有什么其他的操作会受到影响？
Question 2: Would I be able to achieve O(logn) efficiency on push() if I used a set (or multiset) instead of a vector for the implementation of the priority_queue? What would the consequences be of doing this? What other operations would suffer as a consequence?
注意：我担心这里的时间效率，而不是空间。
推荐答案
优先级队列适配器使用标准库堆算法来构建和访问队列 - 这些算法的复杂性应该在文件。
The priority queue adaptor uses the standard library heap algorithms to build and access the queue - it's the complexity of those algorithms you should be looking up in the documentation.
top（）操作显然是O（1），但可能你想在调用它之后弹出（）堆（根据）是O（2 * log（N）），push（）是O（log（N） ） - 相同的来源。
The top() operation is obviously O(1) but presumably you want to pop() the heap after calling it which (according to Josuttis) is O(2*log(N)) and push() is O(log(N)) - same source.
从C ++标准，25.6.3.1，push_heap：
And from the C++ Standard, 25.6.3.1, push_heap :
和pop_heap：
这篇关于STL priority_queue的效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！