C++ priority_queue

Question

我正在研究如何在 O(n) 时间内构建堆，我发现它使用 Heapify。但我想知道 STL priority_queue 是否也这样做？所以我的问题是：

STL中priority_queue使用了哪种构建堆的方法？ 是使用 heapify 可以将整个数组变成堆 O(n) 还是使用一个一个地插入堆中的元素花费 O(n log n) 时间？

我猜这是第二种方法，因为我们在使用 STL priority_queue 时手动一个一个地插入元素。我说得对吗？

Answer 1

有std::make_heap(...)，它一次接受整个N范围来构建堆。

并且如标准中所述，它具有 O(N) 复杂性。例如，您可以看到 CLang 如何实现 std::make_heap、source is here.

以后如果需要的话，可以在O(log N)时间内使用std::push_heap and std::pop_heap逐一添加和取出元素。

也如 by @Jarod42 you can use just std::priority_queue，因为它的构造函数之一接受具有 N 个元素的范围（迭代器），所以此构造函数也具有 O(N) 复杂性。