Search code examples
data-structuresfunctional-programmingsoft-heap

Purely functional soft heap


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


Solution

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