41

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

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

和

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

我之前假设是，那将是一个top()（我首先选择的两个原因） - 但文档既没有证实也没有否认这个假设。O(1)push()O(logn)priority_queue

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

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

使用priority_queuea vector（默认情况下）作为堆，其中：

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

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

问题1：这是正确的吗？（top()访问是O(1)和push()是O(n)？）

问题 2：如果我使用 a (or ) 而不是 a来实现 ，我能否O(logn)提高效率？这样做会有什么后果？其他哪些操作会因此受到影响？push()setmultisetvectorpriority_queue

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

4

6 回答 6

38

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

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

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

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

和pop_heap：

复杂性：最多 2 * log(last - first) 比较。

于 2010-06-04T13:20:49.640 回答
7

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

push()-

  • 插入向量 - 0(1) 摊销

  • push_into_heap - 最多 log(n) 个比较。O（登录）

    所以 push() 复杂度是 -- log(n)

于 2010-06-04T13:28:42.350 回答
5

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

于 2010-06-04T13:24:43.547 回答
2

如果底层数据结构是堆，top() 将是常数时间，而 push（编辑：和 pop）将是对数的（就像你说的那样）。向量仅用于存储这些内容，如下所示：

堆：
             1
        2 3
      8 12 11 9

VECTOR（用于存储）

1 2 3 8 12 11 9

你可以把它想象成位置 i 的子元素是 (2i) 和 (2i+1)

他们使用向量是因为它按顺序存储数据（这比离散的更高效且缓存友好）

不管它是如何存储的，应该总是实现一个堆（尤其是由制作 STD 库的神），这样 pop 是恒定的，push 是对数的

于 2010-06-04T13:24:20.637 回答
2

C++ STL priority_queue底层数据结构是Heap数据结构（Heap是一种基于完全二叉树的非线性ADT，完全二叉树是通过vector（或Array）容器实现的。

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).
于 2015-04-04T19:09:43.827 回答
1

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：set不能用作priority_queue（不是序列）的底层容器，但可以使用 set 来实现具有O(log n) push()and的优先级队列pop()。但是，这可能不会胜过std::priority_queue过度std::vector实施。

于 2010-06-04T13:31:10.030 回答