C++ priority_queue

Question

我正在寻找如何在O(n)时间内构建一个堆，我使用Heapify找到了它。但我想知道STL priority_queue是否也做了同样的事情？所以我的问题是：

priority_queue在STL中使用哪种堆构建方法？是使用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和std::pop_heap添加和取出1个元素。

作为@Jarod42的suggested，你可以只使用std::priority_queue，因为它的一个构造器接受有N个元素的范围(迭代器)，这个构造器也有O(N)复杂度。