优先级队列堆

Question

是否有任何方法来初始化具有O(N)复杂性的元素的优先级队列？可能使用heapify算法。

我搜索了那个问题，但没有找到解决办法。而且，我知道make_heap()，但这是另外一回事，而不是关于优先级队列。

Answer 1

是否有任何方法来初始化具有O(N)复杂性的元素的优先级队列？

是的；std::priority_queue<...>有一个构造函数。queue给出了这个例子：

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

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

编辑了来回复评论：

堆成最小堆的比较函数是什么？我知道有一个名为there ()的函数，但由于某种原因，它似乎无法在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或更高版本肯定会使其更干净。:-)