C ++中优先级队列的时间复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/44650882/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time complexity of a Priority queue in C++
提问by Kshitij Kohli
Creating a heap takes O(n) time, while inserting into a heap ( or priority queue ) takes log(n) time. Taking n inputs and inserting them into the priority queue, what would be the time complexity of the operation. O(n) or O(n*log(n)).
创建堆需要 O(n) 时间，而插入堆（或优先级队列）需要 log(n) 时间。取 n 个输入并将它们插入优先级队列，操作的时间复杂度是多少。O(n) 或 O(n*log(n))。
Also, the same result would hold in case of emptying the entire heap too ( ie n deletions ), right?
此外，如果清空整个堆（即 n 次删除），同样的结果也会成立，对吗？
回答by Jim Mischel
If you have an array of size nand you want to build a heap from all items at once, Floyd's algorithm can do it with O(n) complexity. See Building a heap. This corresponds to the std::priority_queue constructorsthat accept a container parameter.
如果您有一个大小的数组，n并且想要一次从所有项目构建一个堆，Floyd 算法可以以 O(n) 的复杂度来完成。请参阅构建堆。这对应于接受容器参数的std::priority_queue 构造函数。
If you have an empty priority queue to which you want to add nitems, one at a time, then the complexity is O(n * log(n)).
如果您有一个空的优先级队列要向其添加n项目，一次一个，那么复杂度为 O(n * log(n))。
So if you have all of the items that will go into your queue before you build it, then the first method will be more efficient. You use the second method--adding items individually--when you need to maintain a queue: adding and removing elements over some time period.
因此，如果您在构建队列之前拥有将进入队列的所有项目，那么第一种方法将更有效。当您需要维护队列时，您可以使用第二种方法——单独添加项目：在一段时间内添加和删除元素。
Removing nitems from the priority queue also is O(n * log(n)).
n从优先级队列中删除项目也是 O(n * log(n))。
Documentation for std::priority_queueincludes runtime complexity of all operations.
std::priority_queue 的文档包括所有操作的运行时复杂性。
