c++ - 具有自定义比较器和 O(n) 时间的 priority_queue c++

Question

我正在搜索，但没有找到使用自定义比较器创建priority_queue 的简单方法，但这也需要线性时间来创建priority_queue 中的元素。

可以使用以下方法在线性时间内创建一个 priority_queue：

vector<int> arr = {1,2,3,4};
priority_queue<int> pq(arr.begin(),arr.end());

并且可以使用自定义比较器创建 priority_queue

auto cmp = [](int p1, int p2){return p1<p2};
priority_queue<int,vector<int>,decltype(cmp)> pq(cmp);

我想知道是否可以做这样的事情：

priority_queue<int,vector<int>,decltype(cmp)> pq(cmp,points.begin(),points.end());

因为如果我使用自定义比较器创建 priority_queue 并在使用 push 插入值之后，时间复杂度将为 O (nlg (n))

标签： c++constructorfindc++17priority-queue

Answer 1

Assuming points is a container containing std::vector<int>s, this is how you could define your priority queue:

std::priority_queue<std::vector<int>,
                    std::vector<std::vector<int>>,
                    decltype(cmp)> pq(points.begin(), points.end(), cmp);

Demo