c++ - C++ 中优先级队列的时间复杂度

Question

创建堆需要 O(n) 时间，而插入堆(或优先级队列)需要 O(log(n)) 时间。

取 n 个输入并将它们插入优先级队列，操作的时间复杂度是多少？ O(n) 或 O(n*log(n))。

此外，如果清空整个堆(即 n 次删除)，同样的结果也会成立，对吧？

Answer 1

如果您有一个大小为 n 的数组，并且您想要一次从所有项目构建一个堆，Floyd 的算法可以用 O(n) 的复杂度来完成。参见 Building a heap .这对应于 std::priority_queue constructors接受容器参数。

如果您有一个空的优先级队列，您希望向其中添加 n 个项目，一次一个，那么复杂度为 O(n * log(n))。

因此，如果您在构建队列之前拥有所有要进入队列的项目，那么第一种方法会更有效。当您需要维护一个队列时，您可以使用第二种方法——单独添加项目:在一段时间内添加和删除元素。

从优先级队列中移除 n 项也是 O(n * log(n))。

std::priority_queue 的文档包括所有操作的运行时复杂性。