CODEWITHSUNDEEP
c++algorithmstlheappriority-queue
Erdem Kirez
Erdem Kirez

Reputation: 33

Priority Queue Heapify

Is there any way to initialize priority queue with some elements in O(N) complexity? Using the heapify algorithm possibly.

I searched about that problem but couldn't find a solution. Also, I'm aware of make_heap(), but it's another thing and not about priority queues.

Upvotes: 3

Views: 2970

Answers (1)

ruakh
ruakh

Reputation: 183241

Is there any way to initialize priority queue with some elements in O(N) complexity?

Yes; std::priority_queue<...> has a constructor for this. https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue gives this example:

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

which initializes c3 to a priority queue (max-heap) containing the elements of vec.

Edited to reply to a comment:

what would be the compare function to heapify into a min-heap? I know there is a function called greater<int>(); but it doesn't seem to work for some reason on c++14

So, std::less is a bit of a special case, so maybe it's misleading to use it as an example. The std::priority_queue class template actually takes three type parameters: the element-type, the container-type, and the comparator-type. In the above example, these are int, std::vector<int>, and std::less<int>, respectively. The reason we don't have to write the container-type and comparator-type explicitly in the above example is that those two type parameters have defaults, and in the above example, the default is exactly what we wanted.

To use std::greater<int> instead, the equivalent to the above would be:

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

But if you're using C++17 or higher, you can completely drop the list of template arguments and let the compiler deduce it:

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

(Note: this is not the same as writing std::priority_queue<int> — including any list of template arguments would tell the compiler that you want it to use the defaults for unspecified arguments, rather than using template argument deduction.)

If you're stuck on C++14 and want to avoid having to write std::greater<int>() twice, then a slight improvement is to use one of the constructors that doesn't require a comparator object:

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

But using C++17 or higher definitely makes this cleaner. :-)

Upvotes: 5

Related Questions