c++ - STL priority_queue 的效率

Question

我有一个应用程序 (C++)，我认为 STL priority_queue 可以很好地提供服务。 The documentation说:

Priority_queue is a container adaptor, meaning that it is implemented on top of some underlying container type. By default that underlying type is vector, but a different type may be selected explicitly.

和

Priority queues are a standard concept, and can be implemented in many different ways; this implementation uses heaps.

我之前假设 top() 是O(1)，而push()将是 O(logn) (我首先选择 priority_queue 的两个原因) - 但文档既不确认也不否认这一假设。

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

The complexities of single-element insert and erase are sequence dependent.

priority_queue 使用 vector(默认)作为堆，其中:

... supports random access to elements, constant time insertion and removal of elements at the end, and linear time insertion and removal of elements at the beginning or in the middle.

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

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

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

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

Answer 1

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

top() 操作显然是 O(1) 但大概你想在调用它之后 pop() 堆(根据 Josuttis )是 O(2*log(N)) 并且 push() 是O(log(N)) - 相同的来源。

并且来自 C++ 标准，25.6.3.1，push_heap:

Complexity: At most log(last - first) comparisons.

和pop_heap:

Complexity: At most 2 * log(last - first) comparisons.