Ksh*_*hli 6 c++ algorithm big-o priority-queue
创建堆需要O(n)时间,而插入堆(或优先级队列)需要log(n)时间.取n个输入并将它们插入优先级队列,操作的时间复杂度是多少.O(n)或O(n*log(n)).
同样,在清空整个堆的情况下也会保持相同的结果(即n个删除),对吧？
Jim*_*hel 10
如果你有一个大小的数组,n并且你想同时从所有项目构建一个堆,Floyd的算法可以用O(n)复杂度来做.请参阅构建堆.这对应于接受容器参数的std :: priority_queue构造函数.
如果您有一个空的优先级队列,您想要一次添加n一个项目,那么复杂度为O(n*log(n)).
因此,如果您在构建之前拥有将进入队列的所有项目,那么第一种方法将更有效.当您需要维护队列时,可以使用第二种方法 - 单独添加项目:在一段时间内添加和删除元素.
n从优先级队列中删除项目也是O(n*log(n)).
std :: priority_queue的文档包括所有操作的运行时复杂性.