Concurrent Clean : Heapモジュール

Heapを作ったのだけれど、よく考えると、あんな単純なヒープではちょっと使いどころが微妙で、decrease keyとかできる必要がある。それをするには対象のキーがヒープの中のどこにあるのかが定数オーダーで発見できなければいけないけれど、そういう構造にはなっていないな。
どういう風に組んでおくのが汎用的に使い易いのだろう？