我正在寻找如何在 O(n)
时间内构建一个堆,我发现它使用 Heapify
。但我想知道 STL priority_queue
是否也这样做?所以我的问题是:
STL中的priority_queue
使用了哪种构建堆的方法?
是使用可以在 O(n)
中将整个数组转换为堆的 heapify 还是在 O(n log n)
时间中使用一个一个地插入堆中的元素?
我猜这是第二种方法,因为我们在使用 STL priority_queue
时手动一个一个地插入元素。我说得对吗?
最佳答案
有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)
的复杂性。
关于C++ 优先队列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/66780137/