C++ 优先队列

Question

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

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

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

Answer 1

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

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

稍后你可以使用std::push_heap和 std::pop_heap用于在 O(log N) 时间内按需添加和取出 1 个元素。

也为 suggested @Jarod42 你可以只使用 std::priority_queue ，因为它的构造函数之一接受具有 N 个元素的范围(迭代器)，所以该构造函数也具有 O(N) 的复杂性。