C++ STL priority_queue的效率
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2974470/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Efficiency of the STL priority_queue
提问by Chris Tonkinson
I have an application (C++) that I think would be well served by an STL priority_queue. The documentationsays:
我有一个应用程序（C++），我认为 STL 可以很好地提供它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_queue 是一个容器适配器，意味着它是在一些底层容器类型之上实现的。默认情况下，底层类型是向量，但可以明确选择不同的类型。
and
和
Priority queues are a standard concept, and can be implemented in many different ways; this implementation uses heaps.
优先级队列是一个标准概念，可以通过多种不同方式实现；此实现使用堆。
I had previously assumedthat top()is O(1), and that push()would be a O(logn)(the two reasons I chose the priority_queuein the first place) - but the documentation neither confirms nor denies this assumption.
我以前曾认为那top()是O(1)，那push()将是一个O(logn)（这两个原因，我选择了priority_queue摆在首位） -但文档既不承认也不否认这个假设。
Digging deeper, the docs for the Sequence concept say:
深入挖掘，序列概念的文档说：
The complexities of single-element insert and erase are sequence dependent.
单元素插入和擦除的复杂性取决于序列。
The priority_queueuses a vector(by default) as a heap, which:
在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.
... 支持随机访问元素，常量时间在末尾插入和删除元素，以及在开头或中间线性时间插入和删除元素。
I'm inferring that, using the default priority_queue, top()is O(1)and push()is O(n).
我推断，使用默认的priority_queue，top()是O(1)和push()是O(n)。
Question 1:Is this correct? (top()access is O(1)and push()is O(n)?)
问题 1：这是正确的吗？（top()访问是O(1)和push()是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 vectorfor the implementation of the priority_queue? What would the consequences be of doing this? What other operations would suffer as a consequence?
问题 2：如果我使用 a （或）代替 a来实现 ，我是否能够O(logn)提高效率？这样做的后果是什么？其他哪些操作会因此受到影响？push()setmultisetvectorpriority_queue
N.B.: I'm worried about time efficiency here, not space.
注意：我担心的是时间效率，而不是空间。
采纳答案by Chris Tonkinson
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.
优先队列适配器使用标准库堆算法来构建和访问队列 - 您应该在文档中查找这些算法的复杂性。
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.
top() 操作显然是 O(1) 但大概你想在调用它之后 pop() 堆它（根据Josuttis）是 O(2*log(N)) 和 push() 是 O(log(N) )) - 相同的来源。
And from the C++ Standard, 25.6.3.1, push_heap :
从 C++ 标准 25.6.3.1 开始， push_heap ：
Complexity: At most log(last - first) comparisons.
复杂性：最多记录（最后一个 - 第一个）比较。
and pop_heap:
和 pop_heap：
Complexity: At most 2 * log(last - first) comparisons.
复杂性：最多 2 * log(last - first) 比较。
回答by aJ.
top()- O(1) -- as it just returns the element @ front.
top()- O(1) -- 因为它只返回元素@front。
push()-
push()——
- insert into vector - 0(1) amortized
push_into_heap - At most, log(n) comparisons. O(logn)
so push() complexity is -- log(n)
- 插入向量 - 0(1) 摊销
push_into_heap - 最多 log(n) 次比较。O(登录)
所以 push() 复杂度是 -- log(n)
回答by Yuval F
No. This is not correct. top() is O(1) and push() is O(log n). Read note 2 in the documentation to see that this adapter does not allow iterating through the vector. Neil is correct about pop(), but still this allows working with the heap doing insertions and removals in O(log n) time.
不，这是不正确的。top() 是 O(1) 并且 push() 是 O(log n)。阅读文档中的注释 2 以了解此适配器不允许迭代向量。尼尔关于 pop() 是正确的，但这仍然允许使用堆在 O(log n) 时间内进行插入和删除。
回答by YADAV
C++ STL priority_queue underlying data structure is Heap data structure(Heap is a non linear ADT which based on complete binary tree and complete binary tree is implemented through vector(or Array) container.
C++ STL的priority_queue底层数据结构是堆数据结构（堆是一种非线性ADT，基于完全二叉树，完全二叉树通过向量（或数组）容器实现。
ex Input data : 5 9 3 10 12 4.
Heap (Considering Min heap) would be :
[3]
[9] [4]
[10] [12] [5]
NOW , we store this min heap in to vector,
[3][9][4][10][12][5].
Using formula ,
Parent : ceiling of n-1/2
Left Child : 2n+1
Right Child : 2n+2 .
Hence ,
Time Complexity for
Top = O(1) , get element from root node.
POP()= O(logn) , During deletion of root node ,there is chance to violation of heap order . hence restructure of heap order takes at most O(logn) time (an element might move down to height of tree).
PUSH()= O(logn) , During insertion also , there might chance to violation of heap order . hence restructure of heap order takes at most O(logn) time (an element might move up to root from leaf node).
回答by Bob Fincheimer
If the underlying data structure is a heap, top() will be constant time, and push (EDIT: and pop) will be logarithmic (like you are saying). The vector is just used to store these things like this:
如果底层数据结构是堆，则 top() 将是常数时间，而 push (EDIT: and pop) 将是对数的（就像您说的那样）。向量只是用来存储这些东西是这样的：
HEAP:
1
2 3
8 12 11 9
堆：
1
2 3
8 12 11 9
VECTOR (used to store)
VECTOR（用于存储）
1 2 3 8 12 11 9
1 2 3 8 12 11 9
You can think of it as the element at position i's children is (2i) and (2i+1)
您可以将其视为位置 i 的孩子的元素是 (2i) 和 (2i+1)
They use the vector because it stores the data sequentially (which is much more efficient and cache-friendly than discrete)
他们使用向量是因为它按顺序存储数据（这比离散数据更高效且对缓存友好）
Regardless of how it is stored, a heap should always be implemented (especially by the gods who made the STD lib) so that pop is constant and push is logarithmic
不管它是如何存储的，堆应该总是被实现（特别是由制作 STD 库的大神们），这样 pop 是恒定的，而 push 是对数的
回答by jpalecek
Q1: I didn't look in the standard, but AFAIK, using vector(or dequebtw), the complexity would be O(1)for top(), O(log n)for push()and pop(). I once compared std::priority_queuewith my own heap with O(1)push()and top()and O(log n)pop()and it certainly wasn't as slow as O(n).
Q1：我没有查看标准，但 AFAIK，使用vector（或deque顺便说一句），复杂性将是O(1)for top()、O(log n)forpush()和pop()。我曾经std::priority_queue用O(1)push()andtop()和我自己的堆比较过O(log n)pop()，它肯定没有O(n).
Q2: setis not usable as underlying container for priority_queue(not a Sequence), but it would be possible to use set to implement a priority queue with O(log n)push()and pop(). However, this wouldn't probably outperform the std::priority_queueover std::vectorimplementation.
Q2：set不能用作priority_queue（不是序列）的底层容器，但可以使用 set 来实现优先级队列O(log n)push()和pop()。但是，这可能不会胜过std::priority_queue过度std::vector实现。
