Heap implementations: Fibonacci, Brodal and relaxed

Heap implementations: Fibonacci, Brodal and relaxed

[Hugo Ferreira]

Hello,

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

Re: [Caml-list] Heap implementations: Fibonacci, Brodal and relaxed

[blue storm]

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).

There was a page from Markus Mottl with translated OCaml code from the
book, but he removed it for some obscure reason.

Re: [Caml-list] Heap implementations: Fibonacci, Brodal and relaxed

[Hugo Ferreira]

Hello,

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.


> _______________________________________________
> 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
> 

Re: [Caml-list] Heap implementations: Fibonacci, Brodal and relaxed

[Markus Mottl]

On Mon, Jan 12, 2009 at 12:57 PM, Hugo Ferreira <hmf@inescporto.pt> wrote:
> Still available (Chapter 6.):
>
> http://hg.ocaml.info/release/pure-fun/archive/release-1.0.8.tar.bz2

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.mottl@gmail.com