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 therms 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-based priority queue from an exposed std::vector (by 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.