我有一个应用程序(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:我担心时间效率,而不是空间.