Search code examples
c++heappriority-queue

When should I use make_heap vs. Priority Queue?


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?


Solution

  • 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.