On Sunday, July 10, 2011 6:55:57 PM UTC+1, Jon Harrop wrote: > > In a real program, I'd probably go for binomial heaps if imperative is OK, > FWIW, I found that Okasaki's binomial heaps are among the slowest.
Oops. I meant (imperative) *binary* heaps (the ones that stay in an array and don't need explicit pointers to parents/children to save memory---that's why I was mentioning space use). It's not the first time I say binomial instead of binary ... > Pairing > heaps were the fastest overall, closely followed by leftist heaps in OCaml. > If elements are inserted in order then the leftist heap is ~3x slower than a > pairing heap in OCaml and ~5x slower in F#. Good to know! Another comparison appears in SGB, file miles_span.w, in the context of computing minimum spanning trees. It turns out that Fibonacci heaps are not only a theoretical curiosity! -- Caml-list mailing list. Subscription management and archives: https://sympa-roc.inria.fr/wws/info/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
