I assumed someone would tackle this eventually, but no one ever did. So I made an issue for this: https://github.com/contain-rs/discuss/issues/11
TL;DR decrease_key on a priority queue seems to have some fundamental memory-safety problems to implement maximally efficiently (need reference counting). Someone should implement a (pairing?) heap and do some experiments to see if it’s serious; investigate API design to deal with this.