>あんたが、自前でcompactionを行なうなら、自分でタスクプライオリティに
>従って並び替えをしないといけないし、並び替えをした上で同じ型のcollection同士を
>集めたものを用意してからupdate(vector<T>)のような関数を呼び出す必要がある。

型ごとにheapを持つようにすれば同じ型同士を集める必要はないし、
タスクプライオリティーも、変更されるその都度挿入し直せば、並べ替えを行う必要もなくなる。
当たり前だが、挿入と並べ替えだと、並べ替えの方が重い。

>「型ごとに集めることを考えて、それから並べ替える」ほうが、
>「並べ替えてから型ごとに集める」だとか「その二つを同時に行なう」より速いとは限らないんだが。
>そんな自分のやりやすい方法を言われても。

後者よりも前者の方が常に速い。
前者だと、
１．型ごとに集める処理を端折れる。
２．型ごとに並べ替えた方が速い。なぜなら並べ替えの計算量はO(n*logn)だから。