[Nit: Not "your compiler's" but "your library's." The C++ Standard Library is generally provided by the compiler vendor, but it's not built into the compiler, except for tiny pieces like `std::bad_alloc` and `std::strong_ordering`.]
The implementor has far less freedom than your answer seems to be implying. The standard specifies, for example:
And so on. In fact, if I weren't trying to "yes and" you, I'd say there is essentially no implementation freedom. In particular, the user-programmer is allowed, at any point, to extract the protected data member `c` and verify that it is in fact heapified in the same way that `std::push_heap` would have heapified it.
That said, std::priority_queue::pop is specified to behave "as if by pop_heap followed by pop_back," and in fact the vendor can do better there, by using Floyd's "bottom-up" algorithm. LLVM's libc++ switched from the naïve implementation to Floyd's version back in early 2022, thus closing a feature request that had been open for 11 years at the time:
I think the other two major vendors had already switched by then, although I'm not sure.
The implementation definitely does not have the freedom to switch from the mandated heap-based PQ to any alternative kind of PQ, including but not limited to (TAOCP §5.2.3) "leftist or balanced trees, stratified trees, binomial queues, pagodas, pairing heaps, skew heaps, Fibonacci heaps, calendar queues, relaxed heaps, fishspear, hot queues, etc."
Floyd's algorithm scales worse than the naïve implementation though (for small data elements, when comparisons are cheap).
See "Performance Engineering Case Study: Heap Construction" by Jesper Bojesen, Jyrki Katajainen & Maz Spork
The reason why the naïve algorithm scales better is because with each successive push into the heap, you are likely to hit on the same cache lines (assuming your individual elements aren't the size of the cache line or bigger). This is significantly more important for performance than saving a few comparisons, assuming comparisons are cheap.
Thank you very much for taking the time to comment. One of the motivations for mine was to spur someone else who is much more knowledgeable to provide their thoughts. Thank you.
The implementor has far less freedom than your answer seems to be implying. The standard specifies, for example:
https://eel.is/c++draft/priority.queue#priqueue.cons-4
> The constructor calls make_heap(c.begin(), c.end(), comp).
https://eel.is/c++draft/priority.queue#priqueue.members-5
> emplace calls push_heap(c.begin(), c.end(), comp).
And so on. In fact, if I weren't trying to "yes and" you, I'd say there is essentially no implementation freedom. In particular, the user-programmer is allowed, at any point, to extract the protected data member `c` and verify that it is in fact heapified in the same way that `std::push_heap` would have heapified it.
That said, std::priority_queue::pop is specified to behave "as if by pop_heap followed by pop_back," and in fact the vendor can do better there, by using Floyd's "bottom-up" algorithm. LLVM's libc++ switched from the naïve implementation to Floyd's version back in early 2022, thus closing a feature request that had been open for 11 years at the time:
https://github.com/llvm/llvm-project/commit/79d08e398c17e83b...
I think the other two major vendors had already switched by then, although I'm not sure.
The implementation definitely does not have the freedom to switch from the mandated heap-based PQ to any alternative kind of PQ, including but not limited to (TAOCP §5.2.3) "leftist or balanced trees, stratified trees, binomial queues, pagodas, pairing heaps, skew heaps, Fibonacci heaps, calendar queues, relaxed heaps, fishspear, hot queues, etc."
I once wrote an STL-style implementation of Fishspear, with some analysis of its pros and cons. https://quuxplusone.github.io/blog/2021/05/23/fishspear/