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

问题描述

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

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

和

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

我以前曾经假设 / code>是 O（1），并且 push（）将是 O（logn）（我首先选择 priority_queue 的两个原因） - 但是文档既不确认也不否认这个假设。

进一步深入，Sequence概念的文档说：

复杂性

priority_queue 使用a 向量（默认情况下）作为堆，其中：

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

我推断，使用默认 priority_queue ， top（）是 O（1）和 push（）是 O（n）。

问题1：这是正确的吗？ （ top（）访问 O（1）和 push $ c> O（n）？）

问题2：如果我使用了一个集合，则能够在 push（）上实现 O（logn） （或 multiset ）而不是向量 c> priority_queue ？这样做的后果是什么？其他操作会受到什么影响？

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

b $ b

解决方案

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

top（）操作显然是O（1），但是你可能想要调用它后调用它（根据 Josuttis ）是O（2 * log（N）），push（）是O（log（N）） - / p>

并且从C ++标准，25.6.3.1，push_heap：

复杂性：最多log（最后一个）
比较。

和pop_heap：

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

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

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.

and

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

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.

Digging deeper, the docs for the Sequence concept say:

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

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.

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

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

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?

N.B.: I'm worried about time efficiency here, not space.

解决方案

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

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.

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

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

and pop_heap:

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

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