When should I use make_heap vs. Priority Queue?

Question

I have a vector that I want to use to create a heap. I'm not sure if I should use the C++ make_heap function or put my vector in a priority queue? Which is better in terms of performance? When should I use one vs. the other?

Answer 1

There's no difference in terms of performance. std::priority_queue is just an adapter class that wraps the container and the very same heap-related function calls into a class. The specification of the std::priority_queue openly states that.

By building a heap from an exposed std::vector and calling heap-related functions directly, you keep it open to the possibility of outside access, potentially damaging the integrity of the heap/queue. std::priority_queue acts as a barrier restricting that access to a "canonical" minimum: push(), pop(), top() etc. You can see it as self-discipline enforcing measure.

Also, by adapting your queue interface to the "canonical" set of operations, you make it uniform and interchangeable with other class-based implementations of priority queues that conform to the same external specification.

Answer 2

A priority_queue is (at least normally) implemented as a heap. As such, the real question is whether a priority_queue provides what you need. When you use make_heap you still have access to all elements. When you use priority_queue, you have only a few operations giving very limited access to elements (basically just insert an item, and remove the item at the head of the queue).