优先级队列Heapify

Question

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

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

Answer 1

\n

有没有办法用 O(N) 复杂度的一些元素来初始化优先级队列？

\n

\n

是的; std::priority_queue<...>有一个为此的构造函数。https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue给出了以下示例：

\n

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

\n

它初始化c3为包含 的元素的优先级队列（最大堆）vec。

\n\n

编辑回复评论：

\n

\n

堆化为最小堆的比较函数是什么？我知道有一个函数叫greater<int>(); 但由于某种原因它似乎在 c++14 上不起作用

\n

\n

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

\n

要std::greater<int>改为使用，与上面的等效内容是：

\n

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

\n

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

\n

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

\n

（注意：这与编写包含任何模板参数列表的 \xe2\x80\x94 不同，这会std::priority_queue<int>告诉编译器您希望它使用未指定参数的默认值，而不是使用模板参数推导。）

\n

如果您陷入 C++14 并希望避免编写std::greater<int>()两次，那么一个小小的改进是使用不需要比较器对象的构造函数之一：

\n

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

\n

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

\n