Re: [Caml-list] Priority queues, reloaded

[Wojciech Meyer <wojciech.meyer@googlemail.com>]

Gabriel Scherer <gabriel.scherer@gmail.com> writes:

> The heap implementation in the OCaml manual, which was pointed to in
> the precedent thread, is quite compact.
>
> Okasaki (eg. in its book "Purely functional data structure", but can
> probably be found in papers available on the net) has a "leftist heap"
> data structure that is also compact and, to my personal taste, easier
> to understand, get familiar with and remember than the usual heap
> implementation -- or more exotic heaps. I was once in a situation
> similar to yours and found that I could implement both his leftist
> heap and the red-black trees in around 15 minutes.

Yes, they are nice, and I'd also recommend reading whole book if you
have some time for a good lecture. The examples are in Standard ML so
it's nearly direct translation to OCaml. I think it was mentioned but
Markus Mottl has implemented Okasaki's data structures in OCaml and made
it available on his website.  One thing to note is that you don't need
really laziness in case of leftitst heaps and red-black trees, as far as
I recall both are amortised.

Cheers;
Wojciech

>
> On Thu, Jun 30, 2011 at 7:13 PM, Andrew <newsgroups.fr@gmail.com>
> wrote:
>
>     Hi all,
>     
>     Since the previous discussion regarding priority queues pretty
>     much concluded that they weren't available in OCaml, could you
>     point to the most compact implementation that you know of? I'm
>     very likely to have to recode my own implementation in a
>     time-restricted setting, so I'd love to hear about
>     efficient-yet-easy/fast-to-implement options.
>     
>     Thanks!
>     
>     -- 
>     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
>     
>