What heap structure does C++ STL priority queue use?

Question

Specifically, what heap variant does the STL priority queue container adaptor use? I'm benchmarking it vs my own hand rolled binary heap and double bucket structure implementations, so just wondering. Bonus points for any interesting implementation knowledge!

Answer 1

This question is tagged C++ (as opposed to asking for implementation-specific details on a particular compiler), so I've checked the standard for any information. In various sections of 23.6.4 we learn that the priority_queue simply behaves as-if it uses make_heap, push_heap, and pop_heap. Then these functions are documented (in 25.4.6 sections) as having complexity At most 3 * (last - first) comparisons., At most log(last - first) comparisons., and At most 2 * log(last - first) comparisons. respectively. So certain heap implementations may be indicated by these characteristics, but no specific heap is called out.

Answer 2

You can choose the container underlying the priority_queue. If not specified the default is to use a std::vector:

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

Container - The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer. Additionally, it must provide the following functions with the usual semantics: front() push_back() pop_back() The standard containers std::vector and std::deque satisfy these requirements.

The heap is implemented by the *_heap functions, in a straightforward way. You can inspect the code here: http://www.sgi.com/tech/stl/stl_heap.h