在 C++ 标准库文档中搜索某些函数时，我读到优先级队列的推送和弹出需要恒定的时间。
http://www.cplusplus.com/reference/stl/priority_queue/push/
常量（在 priority_queue 中）。尽管请注意 push_heap 以对数时间运行。
我的问题是使用什么样的数据结构来维护优先级队列，其中 O(1) 用于 push 和 pop ？
1783 次
6 回答
9
我假设您指的是cplusplus.com 的页面。
在页面的前面它说：
该成员函数有效调用底层容器对象的成员函数push_back，然后调用push_heap算法来保持priority_queues的堆属性。
因此，在O(1)推送之后，数据结构失去了其堆属性不变性，然后将始终跟随O(log N)调用来恢复该属性。也就是说，O(1)操作只是整个操作的一部分；完整的操作O(1) + O(log N)与O(log N).
我猜他们提到的原因是优先级队列是一个适配器，他们试图强调底层容器的作用与适配器的作用之间的区别。
于 2010-04-10T15:49:18.933 回答
1
priority_queue 的底层存储可以是向量或双端队列或任何类似的支持随机访问迭代器的东西。存储作为堆维护，推送不是 O(N)，所以我怀疑你读错了
于 2010-04-10T15:45:22.257 回答
0
Push 和 Pop 以对数时间运行，根据
于 2010-04-10T15:43:18.490 回答
0
我对 O(1) 的说法持怀疑态度……你在哪里看到的？
无论如何，这里有一些关于 gcc 实现优先级队列的注释。
于 2010-04-10T15:43:44.063 回答
0
没有这种堆。他们写道，它调用了对数的 push_heap，所以它是 logn。
于 2010-04-10T15:44:14.657 回答
0
push_heap该标准用和定义这些成员pop_heap，这意味着可编译性。
如果那个引用说的是真的（它说top的也是常数），为什么没有人使用 来实现通用的 O(N) 排序std::priority_queue？
不过，在第二个方面，这就是参考可能试图以一种非常误导的方式说的：复杂性是push_backO(1) + push_heap(O(log N))
于 2010-04-10T15:48:04.067 回答