我有一个应用程序 (C++)，我认为 STL 可以很好地服务它priority_queue. 文档 http://www.sgi.com/tech/stl/priority_queue.html says:
Priority_queue 是一个容器适配器，这意味着它是在某些底层容器类型之上实现的。默认情况下，基础类型是向量，但可以显式选择不同的类型。
and
优先级队列是一个标准概念，可以通过多种不同的方式实现；该实现使用堆。
我以前有过assumed that top() is O(1)， 然后push()将是一个O(logn)（我选择的两个原因priority_queue首先） - 但文档既没有证实也没有否认这个假设。
更深入地挖掘，序列概念的文档说：
单元素插入和擦除的复杂性取决于序列。
The priority_queue uses a vector（默认情况下）作为堆，其中：
...支持随机访问元素、在末尾恒定时间插入和删除元素、以及在开头或中间线性时间插入和删除元素。
我推断，使用默认值priority_queue, top() is O(1) and push() is O(n).
问题一：它是否正确？ （top()访问权限是O(1) and push() is O(n)?)
问题2：我能实现吗O(logn)效率上push()如果我用了set (or multiset） 代替vector为实施priority_queue？这样做会产生什么后果？其他哪些业务会因此受到影响？
注意：我担心的是时间效率，而不是空间。
优先级队列适配器使用标准库堆算法来构建和访问队列 - 您应该在文档中查找这些算法的复杂性。
top() 操作显然是 O(1) 但大概你想在调用它之后 pop() 堆（根据Josuttis http://www.josuttis.com/libbook/index.html) 是 O(2*log(N)) ，push() 是 O(log(N)) - 相同的来源。
来自 C++ 标准 25.6.3.1，push_heap ：
复杂性：最多进行 log（最后 - 第一个）比较。
和 pop_heap：
复杂性：最多 2 * log(最后 - 第一个) 比较。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
