I assumed someone would tackle this eventually, but no one ever did. So I made an issue for this: Rust is missing an advanced heap · Issue #11 · contain-rs/discuss · GitHub
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.