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

Question

我正在搜索，但没有找到使用 cumstom 比较器创建 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))

Answer 1

假设 points 是一个包含 std::vector<int>s 的容器，这就是您定义优先级队列的方式：

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

Demo

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

priority_queue c++ with custom comparator and O(n) time

c++

constructor

find

c++17

priority-queue