[Haskell-cafe] Looking for an heap-like data structure allowing efficient update

Arnaud Bailly arnaud.oqube at gmail.com
Sun Mar 4 19:27:11 CET 2012


Hello Cafe,
I am looking for a data structure that would have the following
informal properties:
 - allow efficient retrieval of minimum element for some ordering
relation on a computed property of the elements
 - allow efficient update of any element wrt to this property

I have first tried to use a PQueue from fingertree package but it does
not allow deletion/update of arbitrary elements. I then started to try
combining this with a map but ran into the same issue. I skimmed
through Okasaki's book (oldies but goldies...) and the basic finger
tree structure but these does not seem to fit my needs.

Thanks for your help

Regards,
Arnaud Bailly



More information about the Haskell-Cafe mailing list