Add bootstrapped queues?

[treeowl]

I still don't know how bad the extra internal laziness suggested in #115 might be, but it got me thinking: a strict version of that (i.e., strict in keys and values) would be perfect for implementing a relatively compact bootstrapped MinQueue. And adding a lazy value field in BinomTree yields a half-strict 2-valued queue perfect for implementing a bootstrapped version of MinPQueue. I've written up the basic operations, as well as unordered maps and traversals for the second version. I haven't done any benchmarking yet. Intuitively, I would expect this to be a little slower than our current queues, but likely faster than the bootstrapped skew binomial ones in the heaps package.

So do such queues belong here? There? Their own package?

[konsumlamm]

I once implemented a bootstrapped skew binomial heap and it performed a lot worse than the non-bootstrapped version (however I can't guarantee that my implementation was correct). I don't remember how it compared to heaps though.

Wether such queues belong here depends on the benchmarks, I'd say. If they perform better overall, why not replace the current implementation? If they're only faster for some operations (most likely union, after all that's the point of the bootstrapping), it's probably not worth it.

[treeowl]

Bootstrapped queues essentially delay the cost of union until some later deletion time. So they always have faster union, but that'll be paid for later. I think they likely only make sense when constant-time union is a must (probably for some algorithmic reason). However, in the absence of heavy merging, I doubt they'll be much slower than our current implementation: we currently waste one word per entry that a bootstrapped queue can use for the simple queue of bootstrapped queues; additionally, lazy binomial queues are rather simpler than skew heaps, which is probably a substantial performance improver by itself (at the cost of degrading constant times to amortized constant/worst case logarithmic ones).

---

At the moment, I'm developing the bootstrapped things as a separate package. I expect it to be pretty much done within a day or two, but I could really use your help figuring out what to name both the package and the modules therein.

[konsumlamm]

Unfortunately, I don't have any good suggestions. Perhaps just pqueue.bootstrapped (to indicate that it's related to pqueue)? Although that won't tell you much if you don't know what bootstrapping is.