Adding a persistent priority queue to the package?

[saolof]

Hey, so first of all I wanted to say that I find this crate very useful. The main current omission is the lack of a persistent priority queue (ordered dicts and sets do not allow for multiple elements out of the box). Creating & microoptimizing one should be a fun problem; there is a fairly large design space of possible designs for an efficient priority queue (in fact, half of Okasaki's book on data structures literally seems to be about various heaps), so I felt that creating an issue here as a space to discuss various possible options including practical performance considerations,linking research papers & resources, and benchmarking of various options could be a good idea.

The first question would of course be which operations to prioritize. Since the mutable standard library bin-heap has abysmal merge-heap performance but fast everything-else and cannot persistently share data with earlier versions of itself, as a complementary design here it may be a good idea to pick one with fast O(log(n)) or O(1) merges and good performance as a persistent data structure.

With that said, since cache locality matters in the real world, a good starting point may be to consider a simple 32-ary heap with copy-on-write depending on node refcounts (so that inserts and pops would only need six heap accesses), and using it as a benchmark to compare any alternative implementation to.

( Edit: Incidentally, here's a nice paper by Larkin/Sen/Tarjan studying a range of mutable heaps, and finding that even in that domain it is not true that binary heaps are always king: https://arxiv.org/pdf/1403.0252.pdf )