Is there any “stock” implementation of min-heap which allows to decrease a key of arbitrary element?
Usually in imperative languages it’s realized by an array-backed min-heap with additional mapping of key-to-array index, to quickly find the updated element. However all libraries I’ve seen only allow to update a minimal value.
Priority Search Trees or Priority Search Queues (e.g. PSQueue: Priority Search Queue) support O(log n) time updates, and thus also decreasekey, by key. I think it is open/unclear if one could get something better (i.e. since it is unclear how to represent the input to such an update exactly; i.e. in an ephemeral setting you typically get a pointer to the element; that is not really possible in a functionally persistent setting).
Looks like something I was looking for. Many thanks!