Petitverse

マージ可能ヒープを作ろうと思うのですが、マージ可能ヒープが必要な場面に出会ったことがないため、複数ヒープを持つときのヒープの持ち方で困っています。
最初deque(push,pop,shift,unshiftが可能な配列)で持とうと思いましたが、マージ時に途中の要素を削除する必要があるため、厳しいと思いました。
かと言ってリストで持とうとすると、ランダムアクセスが出来ないので不便な気がします。
ランダムアクセスの必要がないならリストで実装しようと思いますが、ランダムアクセスは必要でしょうか。