Radu Grigore wrote:
On Thursday, June 30, 2011 7:14:56 PM UTC+1, Jean-Christophe Filliâtre wrote:
Le 30/06/2011 19:26, Gabriel Scherer a �crit :
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 [...]
Okasaki probably prefers maxiphobic heaps.
http://www.eecs.usma.edu/webs/people/okasaki/sigcse05.pdf
I confirm that leftist heap is probably the best possible choice.
How is that better than using Set?
The only reason I see for implementing your own heap is to save space: Binomial
heaps have much better constants. (Smaller space& cache will likely lead to
less time.)
Sets are not heaps ; they can't have multiple copies of the same element.
--
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
