STL priority_queue的效率

Question

我有一个应用程序(C++),我认为STL将很好地服务priority_queue. 文件说:

Priority_queue是一个容器适配器,这意味着它是在一些底层容器类型之上实现的.默认情况下,底层类型是vector,但可以显式选择其他类型.

和

优先级队列是标准概念,可以通过多种不同方式实现; 这个实现使用堆.

我以前认为那top()是O(1),那push()将是一个O(logn)(我首先选择的两个原因priority_queue) - 但文档既没有证实也没有否定这个假设.

深入挖掘,序列概念的文档说:

单元素插入和擦除的复杂性依赖于序列.

在priority_queue使用vector作为堆,其(默认):

...支持随机访问元素,在末尾插入和删除元素,以及在开头或中间插入和删除元素的线性时间.

我推断,使用默认的priority_queue,top()是O(1)和push()是O(n).

问题1:这是正确的吗？(top()访问是O(1)和push()是O(n)？)

问题2:如果我使用(或)而不是a 来实现,我是否能够实现O(logn)效率？这样做的后果是什么？其他什么操作会受到影响？push()setmultisetvectorpriority_queue

NB:我担心时间效率,而不是空间.

Answer 1

优先级队列适配器使用标准库堆算法来构建和访问队列 - 这是您应该在文档中查找的那些算法的复杂性.

top()操作显然是O(1),但可能你想在调用它之后pop()堆(根据Josuttis)是O(2*log(N))而push()是O(log(N) )) - 相同的来源.

从C++标准,25.6.3.1,push_heap:

复杂性:至多对数(最后 - 第一)比较.

和pop_heap:

复杂性:最多2*log(最后 - 第一)比较.

Answer 2

top() - O(1) - 因为它只返回元素@front.

push() -

Answer 3

不,这不对.top()是O(1),push()是O(log n).阅读文档中的注释2,看看此适配器不允许迭代向量.关于pop(),Neil是正确的,但是这仍然允许在O(log n)时间内使用堆进行插入和删除.