STLpriority_queue的效率

Question

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

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

和

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

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

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

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

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

...支持随机访问元素、末尾固定时间插入和删除元素、开头或中间线性时间插入和删除元素。

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

问题 1：这是否正确？ （top() 访问是 O(1)，push() 是 O(n)？)

< strong>问题 2：如果我使用 set，我能否在 push() 上实现 O(logn) 效率（或multiset）而不是vector来实现priority_queue？这样做会产生什么后果？其他哪些操作会因此受到影响？

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

Answer 1

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

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

来自 C++ 标准 25.6.3.1，push_heap ：

复杂性：最多进行 log（最后 - 第一个）比较。

和 pop_heap：

复杂性：最多 2 * log（最后 - 第一个）比较。

Answer 2

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

push() -

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

• push_into_heap - 最多 log(n) 次比较。 O(logn)

  所以push()的复杂度是——
  log(n)

Answer 3

不，这是不正确的。 top() 的复杂度为 O(1)，push() 的复杂度为 O(log n)。请阅读文档中的注释 2，了解该适配器不允许迭代向量。 Neil 关于 pop() 的说法是正确的，但这仍然允许在 O(log n) 时间内使用堆进行插入和删除操作。

Answer 4

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

HEAP：
          1
      2        3
     8 12 11 9

VECTOR (用于存储)

1 2 3 8 12 11 9

你可以将其视为位置 i 的子元素的元素是 (2i) 和 (2i+1)

他们使用向量是因为它顺序存储数据（这比离散的效率高得多，而且对缓存友好）

无论如何存储，都应该始终实现堆（尤其是制作 STD lib 的大神们），这样 pop 是恒定的，push 是对数的

Answer 5

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).

Answer 6

Q1：我没有查看标准，但据我所知，使用 vector （或 deque 顺便说一句），复杂度将是 O(1) 对于 top()，O(log n) 对于 push() 和 pop()。我曾经使用 O(1) push() 和 top() 将 std::priority_queue 与我自己的堆进行比较> 和 O(log n) pop() 并且它肯定没有 O(n) 慢。

Q2：set 不能用作 priority_queue 的底层容器（不是序列），但可以使用 set 来实现优先级队列 O( log n) push() 和 pop()。但是，与 std::vector 实现相比，这可能不会优于 std::priority_queue 。