On Wed, Feb 14, 2024 at 2:03 PM David G. Pickett via Std-Proposals <std-proposals@lists.isocpp.org> 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—

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.

$ 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