在C++标准库文档中搜索某些函数时，我阅读推送和弹出优先级队列需要一段时间。使用优先级队列结构吗？
http://www.cplusplus.com/reference/stl/priority_queue/push/
常数（在priority_queue）。虽然注意到push_heap在对数时间运行。
我的问题是什么样的数据结构被用来维护一个优先级队列与O（1）推和弹？根据
http://www.cppreference.com/wiki/stl/priority_queue/pop
http://www.cppreference.com/wiki/stl/priority_queue/push
我承担你指的是cplusplus.com's page。
它说在页面上早些时候：
该成员函数有效地调用底层的容器对象的成员函数的push_back，然后调用push_heap算法，以保持priority_queues的堆属性。
因此，O(1)推后，数据结构已经失去了堆属性不变，并随后将始终遵循与O(log N)呼叫，以恢复该属性。换句话说，O(1)操作只是整个操作的一部分;完整的操作是O(1) + O(log N)，这与O(log N)相同。
我猜他们提到的原因是，优先级队列是一个适配器，他们试图强调底层容器与适配器的作用之间的区别。
Push和Pop运行对数时间？
在任何情况下，这里是some notes on gcc's implementation of a priority queue。
我怀疑的O（1）要求......你在哪里看到它
没有这样的堆。他们写道，它调用push_heap，这是对数，所以它是logn。
priority_queue的底层存储可以是支持随机访问迭代器的矢量或双端队列或任何类似的东西。存储保持为堆，这是不针对push O（N），所以我怀疑您已阅读本错
该标准定义了在push_heap和pop_heap，这意味着该术语compilexity那些成员。
如果that reference说的是真的（说top也是常量），为什么没有人使用std::priority_queue实现通用的O（N）排序？
在第二虽然，这是个什么可以参考想说，在一个非常误导的方式：复杂是，push_back O（1）+ push_heap（O（日志N））
你从哪里读到的？ – 2010-04-10 15:42:01
http://www.cplusplus.com/reference/stl/priority_queue/push/ – 2010-04-10 15:43:19