二分ヒープデータ構造への要素の挿入と削除アルゴリズムを解説

はじめに

本記事では、二分ヒープ（バイナリヒープ）というデータ構造に対して、要素を挿入および削除する方法について詳しく解説します。二分ヒープは、優先度付きキューの実装などに広く活用される重要なデータ構造です。説明のために、以下のような初期状態の木を想定します。

挿入アルゴリズム

ヒープへの要素の挿入は、まず新しい要素をヒープの末尾に追加し、その後、ヒープの性質（親ノードが子ノード以上の値を持つ）を満たすように、適切な位置まで要素を上方へ移動させることで行います。この操作は「アップヒープ（上浮き）」とも呼ばれます。

以下が挿入のアルゴリズムです。

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

挿入の例

それでは、このヒープに30を挿入する場合を考えてみましょう。

挿入後もヒープの性質が保たれていることが確認できます。

削除アルゴリズム

ヒープからの削除は、通常、ルート（最大ヒープの場合は最大値）を取り除く操作を指します。削除後は、最後の要素をルートに移動し、ヒープの性質を満たすまで子ノードと比較しながら下方へ移動させます。この操作は「ダウンヒープ（下沈み）」とも呼ばれます。

以下が削除のアルゴリズムです。

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

削除の例

次に、最終的なヒープから30を削除する場合を考えてみましょう。

まとめ

二分ヒープへの挿入と削除は、いずれも木の高さに比例するO(log n)の計算量で実行できます。挿入では要素を末尾に追加して上方へ調整し、削除では最後の要素をルートに移動して下方へ調整することで、常にヒープの性質を維持します。この効率性により、二分ヒープは優先度付きキューやヒープソートなど、さまざまなアルゴリズムの基盤として活用されています。