最大ヒープへの挿入アルゴリズムをわかりやすく解説｜二分ヒープの基本操作

本記事では、二分最大ヒープ（Max Heap）というデータ構造に新しい要素を挿入する方法について詳しく解説します。ヒープは優先度付きキューの実装などで広く使われる重要なデータ構造であり、挿入操作の仕組みを理解することはアルゴリズム学習の基礎となります。

まず、以下のような初期状態のヒープ（完全二分木）を想定します。

最大ヒープへの挿入アルゴリズム

最大ヒープへの挿入は、次の手順で行われます。

1. ヒープに空きがあるか確認し、満杯であれば処理を終了します。
2. 新しい要素をヒープの末尾（配列の最後の位置）に仮置きします。
3. 親要素と値を比較しながら、親より大きい場合は親と入れ替えて上へ移動させます（この操作を「アップヒープ化」または「遡上（percolate up）」と呼びます）。
4. 適切な位置に到達した時点で挿入完了です。

擬似コード

insert(heap, n, item) −
Begin
    if heap is full, then exit
    else
        n := n + 1
        for i := n, i > 1, set i := i / 2 in each iteration, do
            if item <= heap[i/2], then break
            heap[i] = heap[i/2]
        done
    end if
    heap[i] := item
End

このアルゴリズムでは、変数 n は現在のヒープの要素数を表し、i/2 によって親ノードの位置を計算しています。挿入する値が親以下であればループを抜け、その位置に値を格納することでヒープの性質（親 ≥ 子）が保たれます。

具体例：30 をヒープに挿入する

それでは、実際に上記のヒープへ値 30 を挿入してみましょう。まず30を末尾に配置し、親ノードとの大小比較を繰り返しながら適切な位置まで移動させます。手順は以下の図の通りです。

計算量について

挿入操作では、最悪の場合でも要素が根から葉までの高さ分しか移動しません。そのため、n 個の要素を持つヒープへの挿入の計算量は O(log n) となり、非常に効率的です。一方、要素数の更新や位置の特定は O(1) で行えます。