Randomized meldable heap とは

コンピュータサイエンスでは、ランダム化された融合可能ヒープ(Meldable HeapまたはRandomized Meldable Priority Queue)が優先順位キューベースのデータ構造であり、その基礎構造もヒープ順のバイナリツリーです。ただし、基本となるバイナリツリーの形状に制限はありません。
このアプローチには、同様のデータ構造に比べて多くの利点があります。ランダム化された融合可能なヒープのすべての操作は実装が簡単で、複雑さの境界内の定数は小さいです。また、バランス条件を維持する必要もなく、ノード内の衛星情報は必要ない。最後に、この構造は良好な最悪の場合の時間効率を有する。各個々の操作の実行時間は、多くの場合、高い確率で対数である。