ディープ（Deap）データ構造への要素の挿入方法

ディープ（Deap）への要素の挿入とは

ディープ（Deap：Double-Ended Heap）は、最小ヒープと最大ヒープを1つの完全二分木上に組み合わせたデータ構造であり、最小値と最大値の両方を効率的に扱うことができます。このディープに新しい要素を挿入するには、事前に最小ヒープ側・最大ヒープ側の対応位置を求めるための手続きが必要になります。具体的には、以下の2つの手続きを用います。

最小値側の位置を求める手続き

Procedure min_value(m)：位置 m に対応する最小ヒープ側の位置を計算します。
return m − 2log2(m−1)

最大値側の位置を求める手続き

Procedure max_value(m)：位置 m に対応する最大ヒープ側の位置を計算します。
return m + 2log2(m−1)

挿入操作の手順

ディープへの要素の挿入は、次の流れで実行します。

• 任意のヒープ配列 b[] に対して、挿入位置 m が最大ヒープ側に属するかどうかを確認します。
• 続いて、min_value および max_value を用いて、対応する最小値側・最大値側の位置を計算します。
• 左部分木（最小ヒープ）と右部分木（最大ヒープ）のキー値を比較します。
• 最後に、以下のアルゴリズムに従って実際の挿入操作を行います。

挿入アルゴリズム

以下は、ディープへの要素挿入を表す擬似コードです。挿入対象の値を y、挿入位置を m としています。

Procedure deap_insertion(b[], y, m):
if (m == 1)
    b[2] = y;
else {
    if (m is in maximum subtree) {
        index = min_value(m);
        if (y < b[index]) {
            b[m] = b[index];
            insert y in minimum subtree;
        }
        else
            insert y in maximum subtree;
    } else {
        index = max_value(m);
        if (y > b[index]) {
            b[m] = b[index];
            insert y into maximum subtree;
        }
        else
            insert y into minimum subtree;
    }
}

アルゴリズムのポイント

このアルゴリズムでは、挿入位置が最大ヒープ側にある場合は min_value で対応する最小ヒープ側の要素と比較し、挿入値の方が小さければ元の要素を押し出して最小ヒープ側へ移動させます。逆に、挿入位置が最小ヒープ側にある場合は max_value で対応する最大ヒープ側の要素と比較し、挿入値の方が大きければ同様の処理を行います。これにより、ディープの性質（最小ヒープ側のすべての要素が、対応する最大ヒープ側の要素より小さい）が常に保たれます。