c++ - 优先队列堆化

Question

有没有办法用O(N) 复杂度的某些元素来初始化优先级队列？可能使用 heapify 算法。

我搜索了那个问题，但找不到解决方案。另外，我知道 make_heap()，但这是另一回事，与优先级队列无关。

Answer 1

Is there any way to initialize priority queue with some elements in O(N) complexity?

是的； std::priority_queue<...>为此有一个构造函数。 https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue给出这个例子:

std::vector<int> vec={3, 1, 4, 1, 5};
std::priority_queue<int> c3(std::less<int>(), vec);

初始化c3到包含 vec 元素的优先级队列(最大堆) .

---

编辑回复评论:

what would be the compare function to heapify into a min-heap? I know there is a function called greater<int>(); but it doesn't seem to work for some reason on c++14

所以，std::less有点特殊，所以用它作为例子可能会产生误导。 std::priority_queue类模板实际上采用三个 类型参数:元素类型、容器类型和比较器类型。在上面的示例中，这些是 int , std::vector<int> , 和 std::less<int> ， 分别。我们不必在上面的例子中显式地写容器类型和比较器类型的原因是这两个类型参数有默认值，而在上面的例子中，默认值正是我们想要的。

使用std::greater<int>相反，上面的等价物是:

std::vector<int> vec={3, 1, 4, 1, 5};
std::priority_queue<int, std::vector<int>, std::greater<int>> c3(std::greater<int>(), vec);

但是如果您使用的是 C++17 或更高版本，您可以完全删除模板参数列表并让编译器推断它:

std::vector<int> vec={3, 1, 4, 1, 5};
std::priority_queue c3(std::greater<int>(), vec);

(注意:这不与编写 std::priority_queue<int> 相同 — 包含任何模板参数列表都会告诉编译器您希望它对未指定的参数使用默认值，而不是使用模板论证推导。)

如果您坚持使用 C++14 并希望避免编写 std::greater<int>()两次，然后轻微改进是使用不需要比较器对象的构造函数之一:

std::vector<int> vec={3, 1, 4, 1, 5};
std::priority_queue<int, std::vector<int>, std::greater<int>> c3(vec.cbegin(), vec.cend());

但使用 C++17 或更高版本肯定会使它更干净。 :-)