On Wed, Feb 14, 2024 at 2:03 PM David G. Pickett via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> A binomial heap, min or max, nay be the fastest sort and priority queue.
> It has very high locality of reference, averaging 1/2 log2(N) nodes. [...]
>
> Compared to array based priority queues and to any BST, the push speed is
> O(1) not O(log N), and the locality of reference in mainly just 1/2 log2(N)
> root nodes/values on average. Many array based priority queues also swap
> values up to log(N) times, while a tree based heap does not do repetitive
> swaps. Array based queues have a copy cost to expand if the original or
> last capacity is inadequate, but a heap does not.
>

There are lots of priority queue data structures in the literature, with
different tradeoffs. See Knuth's *TAOCP* §5.2.3 for a whole
bunch: "stratified trees, binomial queues, pagodas, pairing heaps, skew
heaps, Fibonacci heaps, calendar queues, relaxed heaps, fishspear, hot
queues, *etc*."
A few years back I implemented Fishspear in "STL style", a selection made
entirely based on coolness-of-moniker. See this blog post—
https://quuxplusone.github.io/blog/2021/05/23/fishspear/

Quote:

> - By linking elements instead of keeping them contiguous, we lose
> RAM-friendliness but we gain the ability to keep newly inserted items right
> near the top of the data structure instead of having to insert them all the
> way at the bottom. When the shape of the workload makes it likely that “a
> newly inserted element will very soon be deleted,” a classic heap will
> still do O(lg n) comparisons on that element to get it into its proper
> place; Fishspear will do O(1).


> - My C++ version of Fishspear never moves or copies elements, so it can be
> used with immutable types, unlike std::priority_queue.


It also does many fewer comparisons on this specific benchmark
<https://github.com/Quuxplusone/Fishspear/blob/main/bench.cpp> (with a
large queue and relatively short-lived elements):

$ g++ -W -Wall -O2 bench.cpp -o optimized
$ ./optimized
200000 operations (99938 push, 100062 pop) on a queue of initial size 10000
Heap: 3438552 comparisons, 279710 moves, 2504937 assignments, 11
milliseconds
Fishspear: 714652 comparisons, 0 moves, 0 assignments, 28 milliseconds

The moral/punchline here is simply that "some weird-looking priority-queue
structure" may well be worth implementing as a third-party library, but
it's not worth standardizing, because weird-looking priority-queue
structures are a dime a dozen.

–Arthur