I would like to now if anyone has or knows of
functional implementations of priority (aka Min,
aka Max) heaps. Specifically I am looking for:
Fibonacci, Brodal and relaxed heaps [1]
with fast insert and deletes.
Any literature or implementation in Haskell
or F# are also welcome.
I also would appreciate any additional comments on
implementation issues and experience with heaps
that may help me.
TIA,
Hugo Ferreira.
[1] http://en.wikipedia.org/wiki/Fibonacci_heap
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
There was a page from Markus Mottl with translated OCaml code from the
book, but he removed it for some obscure reason.
blue storm wrote:
> First of all, do you know about Okasaki leftist heaps (I suppose you
> do as you're asking for even more advanced data structure) ? They're
> simple O(log n) heap, nice to implement (~ 20 lines).
Actually I didn't (although I know of these). But the thesis has a
better performing binomial heap.
>
> There was a page from Markus Mottl with translated OCaml code from the
> book, but he removed it for some obscure reason.
>
Still available (Chapter 6.):
http://hg.ocaml.info/release/pure-fun/archive/release-1.0.8.tar.bz2
Regards.
Hugo F.
Yes, the OCaml translation of Okasaki's purely functional
datastructures is still available online. The version control
repository, where you can also look at individual files without
downloading the archive, is here:
http://hg.ocaml.info/release/pure-fun
Note that leftist heaps are in chapter 3:
http://hg.ocaml.info/release/pure-fun/file/tip/chp3.ml
Regards,
Markus
--
Markus Mottl http://www.ocaml.info markus...@gmail.com