Deapデータ構造における最小要素の削除方法

はじめに

本記事では、Deapデータ構造から最小要素を削除する手法について詳しく解説します。

Deap（Double-Ended Heap）は、最小ヒープ（min-heap）と最大ヒープ（max-heap）を1つの完全二分木で実現したデータ構造です。左側の部分木が最小ヒープ、右側の部分木が最大ヒープとして機能するため、最小値と最大値の両方に効率的にアクセスできます。

削除操作では、主な目的はDeap内の最小値を取り除くことです。最小値は必ず最小部分木の根（配列のインデックス2の位置）に格納されているため、その位置の要素を取り出すことになります。木の高さは常に log n 程度であるため、削除操作にかかる計算量も O(log n) のオーダーに収まります。

削除アルゴリズムの手順

削除操作は以下の流れで行われます。

1. まず、最小値が格納された b[2] の値を保存します。
2. 削除によって空いた位置を埋めるため、子ノードのうち小さい方を選びながら下方向へたどります。
3. 対応する最大部分木の要素と比較し、ヒープの性質（min-heap性・max-heap性）が崩れないように適切な位置へ要素を挿入し直します。

擬似コード

Procedure deap_deletion(b[], m):
    if(m < 2)
        return; // 要素が存在しない場合
    min = b[2]; // 最小値を保存
    for (i = 2; 2*i <= m; b[i] = b[k], i = k) {
        k = i * 2;
        if(k + 1 <= m && b[k] > b[k+1])
            k++; // 子ノードのうち小さい方を選択
        k = max_value(i); // 対応する最大部分木の要素
        if(x > b[k]) {
            b[i] = b[k];
            insert y into maximum subtree;
        } else {
            insert y into minimum subtree;
        }

コードのポイント

• 要素数のチェック： m < 2 の場合はDeapが空であることを意味するため、何もせず終了します。
• 最小値の保存： b[2] には常に全体の最小値が格納されているため、これを保存して返します。
• 穴埋め処理： 削除で生じた隙間を、子ノードを順に辿りながら埋めていきます。兄弟ノードが存在する場合は、より小さい方の子を選ぶことでmin-heapの性質を保ちます。
• 最大部分木との比較： 対応する最大部分木の要素と値を比較し、条件に応じて挿入先の部分木（min側・max側）を決定します。

計算量について

Deapの高さは O(log n) であり、削除時に辿る経路の長さも木の高さに比例します。したがって、最小要素の削除操作全体の計算量は O(log n) となり、非常に効率的です。

まとめ

Deapからの最小要素の削除は、「最小部分木の根から値を取り出す → 空いた位置を適切な要素で埋める → ヒープ性を維持する」という流れで実現されます。完全二分木という構造上、操作は常に O(log n) で完了するため、優先度付きキューなど双方向の extremum アクセスが必要な場面で有用なデータ構造です。