Are there any implementations of a purely functional soft heap data structure in any language?
+17
A:
A quick search of the ACM digital library indicates that Chazelle's soft heap structure, despite being very interesting, has received relatively little study, and that persistent/functional soft heaps are thus an open research topic.
So I would say no, there are no known approaches for persistent soft heaps. Describing one would be a publishable result (it may boil down to adding copying where you would mutate the original structure, and identifying sharing opportunities).
Don Stewart
2010-08-04 04:07:46
Interesting, thank you.
Jon Harrop
2010-08-04 06:50:58
@Jon, if you plan to tackle this problem, and you haven't read *Purely Functional Data Structures* yet, I suggest you do so. Even though it doesn't cover soft heaps, it will teach you basic principles of functional data structure design that will be helpful in tackling this problem.
Ken Bloom
2010-08-04 13:42:36
@Ken: I've read it, of course. :-)
Jon Harrop
2010-08-04 14:51:35
There is a fairly full-featured OCaml implementation of Okasaki's skew-binomial heaps in my Oni CF library: http://bitbucket.org/jhw/oni
james woodyatt
2010-09-15 01:19:44