I think I reinvented and started implementing something like this, but then just ended up using std::priority_queue (the C++ standard library priority queue) which is pretty fast.
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/
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.
- Look up an arbitrary element by its value, and then change that element's priority. This is often needed in real life, but is fundamentally incompatible with std::priority_queue's highly restricted design. There is no public API at all for dealing with "arbitrary elements" of a std::priority_queue; you interact only with the .top() element.
- Change the top element's priority, i.e. handle it and then throw it back down to be dealt with again sometime later. This operation is used in e.g. the Sieve of Eratosthenes.
I'm not sure which operation you're thinking of w.r.t. Dijkstra's algorithm; I'd wildly guess it's the first operation, not the second.
Changing the top element's priority is easy to graft onto the STL priority_queue's API. I've done it myself here: https://quuxplusone.github.io/blog/2018/04/27/pq-replace-top... The proper name of this operation is `pq.replace_top(value)`, and for the perfect-forwarding version, `pq.reemplace_top(args...)`.
Search `reemplace_top` in this Sieve of Eratosthenes code: https://godbolt.org/z/bvY4Mr1GE
You might argue that is wasteful of space pushing these duplicates, but your other options are either to graft this functionality on to a normal priority queue in which case you're using that space anyway, or to use a much more complex and usually slower kind of priority queue with this operation naturally (e.g. Fibonacci heaps). The space wasted is quite small in practice, since the only time this happens is if multiple nodes on the frontier points to the same element, but most nodes ("in practice") have small degree of incoming paths. The benefit of being able to use standard (and very fast!) priority queues without this weird operation is well worth it.
In my experience of implementing Dijkstra and A-star a couple of dozen times (I like Advent of Code problems!) this has always been the better way to do it. I mean, I haven't put Dijkstra/A-star into production or anything (I don't work for Google Maps or whatever), but in my experience this is the simplest and fastest way in practice to implement these algorithms.
FWIW, my favorite solution for Dijkstra is the winner-tree (a binary heap except that all the nodes are in leaves, so the interior nodes are duplicates). Simple to implement, O(log n) insert/delete/update, can be made branch-free in important cases, constant extra overhead over a binary heap. I've found it to be _much_ faster in practice than stashing duplicates into a regular maxheap (I'm not sure if I agree with your notion that there are few of them).