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

Question

I was searching but I didnt find an easy way to create a priority_queue using a cumstom comparator but that also takes linear time to create the elements in the priority_queue.

it is possible to create a priority_queue in linear time using:

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

and it is possible to create a priority_queue using a custom comparator

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

I want know if it possible to do something like this:

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

Because if I create the priority_queue using the custom comparator and after I insert the values using push, the time complexity would be O (nlg (n))

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