Add real-time versions?

[treeowl]

I'm really not sure it's worth the trouble, but we could improve the amortized times to worst-case using scheduling. Okasaki's scheme uses a separate schedule, which doesn't seem terribly compact, and his analysis is rather tricky. I think we can do something a bit simpler. The debit invariant allows one debit on the child of a Skip node, and no debits anywhere else. We can arrange to force a node as soon as its parent changes from a Skip to a Cons. To accomplish that, we can arrange to always have access to the first Skip node by linking them together.

data Scheduled rk a = forall xxrk x. Scheduled !(BinomForest rk a) (BinomForest xxrk x)
data BinomForest rk a
   = Nil
     -- The second field points to the next Skip node, or Nil if there is none.
   | forall xxrk x. Skip (BinomForest (Succ rk) a) (BinomForest xxrk x)
   | Cons {-# UNPACK #-} !(BinomTree rk a) !(BinomForest (Succ rk) a)

This gives a somewhat segmented flavor. Another option, of course, might be to use a segmented number system. Doing that with nested types will require type-aligned (nonempty) lists; I'm not sure how complicated it will get. And then there are also skew binomial heaps, which I don't really understand yet.

[treeowl]

I think a skew binomial queue implementing extractMin much the way that we do here might be able to avoid an extra pass to insert individual elements by using skew links on the way up.

[konsumlamm]

I wanted to try to implement a skew-binomial version (I already implemented a skew binomial heap that's strict in it's spine here, but it seems to perform worse than pqueue), but I think it's better to wait for #26, to avoid conflicts.

[treeowl]

@konsumlamm I think it would be great to be able to pit multiple real-time implementations against each other. However, I suspect it will be hard for any of them to compete in practice against #26, since amortized constant/worst case logarithmic insertion and worst-case logarithmic everything else are pretty darn good and the code is relatively simple.

[treeowl]

I suspect that in practice, there's more to win by trying to make the representation a little more compact.

[konsumlamm]

The main advantage of skew-binomial heaps would be worst case O(1) insert, but you can also achieve that with scheduling, as you mentioned, so you're probably right. I haven't been able to make a comparable (in performance) skew-binomial heap so far, but fwiw, I haven't been able to make a comparable lazy binomial heap either... One disadvantage of skew-binomial heaps is that we'd loose the type level encoding of ranks (unless we keep Skip nodes, but in that case we might as well use normal binomial heap, ig).

Do the current amortized complexities also hold when the heap is used persistently?

[treeowl]

The current amortized complexities do indeed hold when the heap is used persistently, unless there's a bug, and that would hold for #26 as well.