最大ヒープ（データ構造）から要素を削除するアルゴリズムをわかりやすく解説

ここでは、二分最大ヒープ（Binary Max Heap）というデータ構造から要素を削除する方法について解説します。まず、次のような初期状態の木を想定してください。

最大ヒープからの削除アルゴリズム

最大ヒープに対する削除操作では、通常「根（ルート）にある最大値を取り除く」処理を行います。削除後も親ノードは常に子ノード以上というヒープ条件を維持しなければならないため、単純に要素を取り除くだけでは不十分です。以下の擬似コードのように、末尾の要素を使ってヒープを再構成します。

delete(heap, n) −
Begin
    if heap is empty, then exit
    else
        item := heap[1]
        last := heap[n]
        n := n – 1
        for i := 1, j := 2, j <= n, set i := j and j := j * 2, do
            if j < n, then
                if heap[j] < heap[j + 1], then j := j + 1
            end if
            if last >= heap[j], then break
            heap[i] := heap[j]
        done
    end if
    heap[i] := last
End

アルゴリズムの流れ

1. 空チェック： ヒープが空であれば、そこで処理を終了します。
2. 最大値の取り出し： 根の要素 heap[1] を item として保存します。これが削除対象となる最大値です。
3. 末尾要素の退避： ヒープの最後の要素 heap[n] を last として取り出し、ヒープのサイズ n を1つ減らします。
4. 下向き調整（Sift-Down）： last を根の位置から下へ移動させながら、左右の子のうち大きい方と比較します。last の方が小さければ子を上へ繰り上げ、last が子以上になった時点でループを抜けます。
5. 最終配置： 空いた位置に last を書き込み、ヒープの再構成を完了します。

この操作の計算量は、木の高さに比例する O(log n) であり、非常に効率的な削除手法となっています。

具体例：値 30 の削除

それでは、最終的なヒープから値 30 を削除するケースを考えてみましょう。

まず、削除対象である 30 をヒープから取り出します。続いて、ヒープの末尾にある要素を空いた位置へ移動し、子ノードとの大小関係を比較しながら、ヒープ条件を満たす適切な位置まで沈めていきます（Sift-Down 操作）。この一連の手順により、削除後もヒープ条件が保たれた完全二分木が得られます。