Joh*_*ack 6 c++ algorithm priority-queue data-structures
在C++标准库文档中搜索某些函数时,我读到优先级队列的推送和弹出需要恒定的时间.
http://www.cplusplus.com/reference/stl/priority_queue/push/
常量(在priority_queue中).虽然注意到push_heap在对数时间内运行.
我的问题是使用什么样的数据结构来维护优先级队列,其中包含推送和弹出的O(1)？
我假设你指的是cplusplus.com的页面.
它在页面的前面说:
该成员函数有效地调用底层容器对象的成员函数push_back,然后调用push_heap算法以保持priority_queues的堆属性.
因此,在O(1)推送之后,数据结构已失去其堆属性不变量,然后将始终跟随O(log N)调用以恢复该属性.换句话说,O(1)操作只是整个操作的一部分; 完整的操作O(1) + O(log N)与之相同O(log N).
我猜他们提到的原因是优先级队列是一个适配器,他们试图强调底层容器与适配器之间的区别.