16

Are there any implementations of a purely functional soft heap data structure in any language?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
J D
  • 48,105
  • 13
  • 171
  • 274
  • I got through a bit of it last night; I haven't verified the time complexities, but they seem wrong log( 1/e ) where e is 0 – nlucaroni Aug 05 '10 at 15:11
  • Great! Log is only negative for arguments less than 1 but 1/ε is not because 0<ε<1 so 1<ε⁻¹<∞. – J D Aug 05 '10 at 18:36
  • 1
    Oh, of course. Yes, you are right. I was clearly (or not I suppose), thinking log(ε). So, when he does say that all operations are amortized cost 0, he is talking about a constant factor? – nlucaroni Aug 05 '10 at 18:48
  • 1
    I guess amortized cost 0 means constant factor, yes. – J D Aug 05 '10 at 19:39

3 Answers3

20

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
  • 137,316
  • 36
  • 365
  • 468
  • 3
    @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 Aug 04 '10 at 13:42
  • 1
    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 Sep 15 '10 at 01:19
1

The Haim Kaplan, Robert E. Tarjan, Uri Zwick paper describes but doesn't fully analyze purely functional variant. It can be found at:

http://phdtree.org/pdf/44150182-soft-heaps-simplified/

shaunc
  • 5,317
  • 4
  • 43
  • 58
0

This project has Java code that might not be too terrible to translate to Scala... and then make it more functional.

https://github.com/lowasser/SoftSelect

But as noted previously the Purely Functional Data Structures book has Haskell code that may be easier to adopt to Soft Heaps, especially given the example Java code.

https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

RudeDude
  • 879
  • 6
  • 5
  • I am also looking at this paper from the ACM where SoftHeaps are made with binary trees: http://dl.acm.org/citation.cfm?id=1496823 – RudeDude Jul 07 '14 at 21:43