代码之家 › 专栏 › 技术社区 › Chris Tonkinson

STL优先级队列的效率

priority-queue performance stl data-structures c++

Chris Tonkinson · 技术社区 · 14 年前

我有一个应用程序(C++),我认为它会被STL服务得很好。 priority_queue . The documentation 说:

优先级队列是一个容器适配器,这意味着它是在一些底层容器类型之上实现的。默认情况下,基础类型是vector,但可以显式选择其他类型。

和

优先级队列是一个标准概念,可以通过许多不同的方式实现;此实现使用堆。

我以前 假定的 那个 top() 是 O(1) 那 push() 将是一个 O(logn) (我选择的两个原因 优先队列 首先),但文件既不确认也不否认这一假设。

深入研究,序列概念的文档说:

单个元素插入和擦除的复杂性取决于序列。

这个 优先队列 使用A vector (默认情况下)作为堆,其中:

…支持对元素的随机访问,在末端的元素的恒定时间插入和移除,以及在开始或中间的元素的线性时间插入和移除。

我用默认值推断 优先队列 , () 是 O(1) 和 PUP() 是 O(n) .

问题1: 这是正确的吗?( () 访问是 O(1) 和 PUP() 是 o(n) ?)

问题2: 我能做到吗 o(登录) 效率对 PUP() 如果我用了 set (或) multiset )而不是 矢量 为了执行 优先队列 ?这样做的后果是什么?结果会有什么其他的行动?

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

6 回复 | 直到 8 年前

Danh 8 年前

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

top()操作显然是o(1),但您可能希望在调用堆后弹出(),根据 Josuttis )是O(2*log(n)),push()是O(log(n))-同一个源。

从C++标准,25.63.1,PuthHu堆:

复杂性:最多记录(最后一个-第一个)比较。

罂粟堆:

复杂性:最多2个*对数(前一个)比较。

Yuval F 14 年前

不,这不正确。top()是O(1),push()是O(log n)。请阅读文档中的注释2,以了解此适配器不允许遍历向量。Neil关于pop()是正确的,但这仍然允许在O(log n)时间内处理堆进行插入和删除。

aJ. 14 年前

top() -o(1)--因为它只返回元素@front。

push() -

插入向量-0(1)摊销
将_推入_堆-最多记录(n)个比较。o(登录)

所以push()的复杂性是-- 日志(n)

Bob Fincheimer 14 年前

如果底层数据结构是堆,top()将是常量时间,push(edit:和pop)将是对数(如您所说)。向量只是用来存储如下内容:

堆:
一
2_____3
8 12 12 11 11

矢量(用于存储)

1 2 3 3 8 12 11 9

你可以把它看作是我的孩子在(2i)和(2i+1)位置的元素。

他们使用向量是因为它按顺序存储数据(这比离散存储更高效,缓存更友好)

不管它是如何存储的,都应该始终实现一个堆(尤其是由制造std lib的上帝),这样pop是常量,push是对数的。

YADAV 9 年前

数据结构中的C++ STL优先级队列是堆数据结构(堆是一个基于完全二叉树的非线性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).

jpalecek 14 年前

问题1:我看的不是标准,而是Afaik,使用 vector (或) deque 顺便说一句),复杂性是 O(1) 对于 top() , O(log n) 对于 push() 和 pop() . 我曾经比较过 std::priority_queue 用我自己的堆 O(1) PUP() 和 () 和 O(log n) () 当然也不是那么慢 O(n) .

Q2: set 不能用作的基础容器 priority_queue (不是序列),但可以使用set实现优先级队列 O(log n) PUP() 和 () . 然而,这可能不会比 std::优先级队列 结束 std::vector 实施。