STL priority_queue的效率

Question

我有一个应用程序(C++)，我认为它可以很好地由STL priority_queue提供服务。文献资料说：

Priority_queue是一个容器适配器，这意味着它是在一些底层容器类型之上实现的。默认情况下，基础类型是向量，但可以显式地选择不同的类型。

和

优先级队列是一个标准概念，可以通过多种不同的方式实现；该实现使用堆。

我之前曾假设top()是O(1)，push()将是一个O(logn) (我最初选择priority_queue的两个原因)--但文档既没有证实也没有否认这种假设。

更深入地研究，序列概念的文档说：

单元素插入和擦除的复杂性与序列有关.

priority_queue使用vector (默认情况下)作为堆，它：

..。支持对元素的随机访问，固定时间插入和删除结束元素，线性时间插入和删除元素在开始或中间。

我推断，使用默认的priority_queue，top()是O(1)，push()是O(n)。

问题1:是正确的吗？(top() access是O(1)，push()是O(n)?)

问题2:如果我使用set (或multiset)而不是vector来实现priority_queue，那么能否在push()上实现O(logn)效率？这样做会有什么后果？还有哪些其他行动会因此而受到影响？

注:我担心的是时间效率，而不是空间。

Answer 1

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

top()操作显然是O(1)，但是您可能希望在调用它之后弹出()堆，它(根据乔苏蒂斯)是O(2*log(N))，而push()是O(log(N)) --相同的源。

C++标准，25.6.3.1，push_heap：

复杂性:最多是日志(最后一次)比较。

和pop_heap：

复杂性:最多2*日志(最后-第一)比较。

Answer 2

top() - O(1) -因为它只返回元素@前台。

push() -

• 插入向量- 0(1)摊销
• push_into_heap -至多是log(n)比较。O(logn) 所以push()复杂度是-- log(n)

Answer 3

不是的。这不对。top()是O(1)，push()是O(log )。请阅读文档中的注释2，以确保此适配器不允许遍历向量。Neil对pop()的看法是正确的，但这仍然允许堆在O(log )时间内执行插入和删除操作。