在C++标准库文档中搜索某些功能时，我读到优先级队列的push和pop需要恒定的时间。
http://www.cplusplus.com/reference/stl/priority_queue/push/
我的问题是，什么样的数据结构用于维护带有O(1)的插入和弹出操作的优先级队列？
最佳答案
我假设您指的是cplusplus.com's page。
页面较早的地方说:
因此，在O(1)推送之后，数据结构失去了其堆属性不变，然后将始终跟在它后面，并通过O(log N)调用来恢复该属性。换句话说，O(1)操作只是整个操作的一部分；完整的操作是O(1) + O(log N)与O(log N)相同。
我猜想他们提到优先队列是适配器的原因，并且他们试图强调基础容器和适配器之间的区别。
关于c++ - 使用的优先级队列结构？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2613891/