STL priority_queue的效率 [英] Efficiency of the STL priority_queue

问题描述

我有一个应用程序（C ++），我认为很好地服务于STL priority_queue 。 文档说：

I have an application (C++) that I think would be well served by an STL priority_queue. The documentation says:

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

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（） / code>是 O（1），而 push（）将是一个 O（logn）（我首先选择了 priority_queue 的两个原因） - 但是文档既不确认也不否认这一假设。

I had previously assumed that top() is O(1), and that push() would be a O(logn) (the two reasons I chose the priority_queue in the first place) - but the documentation neither confirms nor denies this assumption.

深入挖掘Sequence序列的文档说：

Digging deeper, the docs for the Sequence concept say:

复杂性单元插入和擦除是依序依赖的。

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

priority_queue 一个矢量（默认情况下）作为堆，其中：

The priority_queue uses a vector (by default) as a heap, which:

...支持对元素的随机访问，最后定期插入和删除元素，以及在开始或中间的元素的线性时间插入和删除。

... 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）。

I'm inferring that, using the default priority_queue, top() is O(1) and push() is O(n).

问题1：这是否正确？ （ top（）访问是 O（1）和 push（）是 O（n）？）

Question 1: Is this correct? (top() access is O(1) and push() is O(n)?)

问题2：如果我使用集合，可以实现 O（logn）效率 push（） （或 multiset ），而不是矢量用于执行 priority_queue ？这样做会有什么后果？还有什么其他的操作会受到影响？

Question 2: Would I be able to achieve O(logn) efficiency on push() if I used a set (or multiset) instead of a vector for the implementation of the priority_queue? What would the consequences be of doing this? What other operations would suffer as a consequence?

注意：我担心这里的时间效率，而不是空间。

推荐答案

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

The priority queue adaptor uses the standard library heap algorithms to build and access the queue - it's the complexity of those algorithms you should be looking up in the documentation.

top（）操作显然是O（1），但可能你想在调用它之后弹出（）堆（根据 Josuttis ）是O（2 * log（N）），push（）是O（log（N） ） - 相同的来源。

The top() operation is obviously O(1) but presumably you want to pop() the heap after calling it which (according to Josuttis) is O(2*log(N)) and push() is O(log(N)) - same source.

从C ++标准，25.6.3.1，push_heap：

And from the C++ Standard, 25.6.3.1, push_heap :

复杂性：大多数日志（最后一个）比较。

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

和pop_heap：

复杂性：最多2 * log（last-first）比较。

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

这篇关于STL priority_queue的效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！