データ構造の学習で「ヒープ木」という言葉に出会った方も多いのではないでしょうか。
「ヒープとヒープ木って同じもの？どんな構造なの？」という疑問をお持ちの方もいるでしょう。
この記事では、ヒープ木とは何か、二分ヒープの構造と性質について、完全二分木・親子関係・ヒープ条件・配列でのインデックス計算まで詳しく解説しています。
データ構造への理解を深めたい方はぜひ最後までご確認ください。
ヒープ木とは？二分ヒープの基本的な概念と定義
それではまず、ヒープ木の基本的な概念と定義について解説していきます。
ヒープ木とは、「二分ヒープ（Binary Heap）」の木構造表現のことであり、完全二分木の形をとりながら親子ノード間の値の大小関係（ヒープ条件）を満たす木構造のことです。
「ヒープ」と「ヒープ木」はほぼ同義で使われることが多く、特に二分ヒープを指すことがほとんどです。
完全二分木の特性とヒープへの応用
完全二分木とは、すべての葉が最下層か最下層のひとつ上の層にあり、最下層の葉は左から詰まっている二分木です。
この特性により、完全二分木は無駄なく配列（1次元の連続したメモリ）として表現できるため、ポインタを使ったリンク構造より効率的です。
また完全二分木の高さはO(log n)（nはノード数）に保たれるため、挿入・削除などの操作がO(log n)で実行できます。
ヒープ条件（Heap Property）の意味
ヒープ木が満たすべき「ヒープ条件」には最大ヒープと最小ヒープの2種類があります。
最大ヒープ条件は「すべてのノードにおいて、親の値≥子の値」であり、根が最大値になります。
最小ヒープ条件は「すべてのノードにおいて、親の値≤子の値」であり、根が最小値になります。
ヒープ条件は親子間のみに適用されるため、同一階層のノード間（兄弟ノード）に大小関係の制約はありません。
ヒープ木の配列表現とインデックス計算の方法
続いては、ヒープ木の配列表現とインデックス計算の方法を確認していきます。
ヒープ木の最大の特徴のひとつが、配列（1次元）で効率よく表現できることです。
配列でのヒープ表現の仕組み
ヒープを0から始まるインデックスの配列で表現する場合、各ノードの親・子のインデックスは次の式で計算できます。
配列インデックスiのノードに対する各ノードの位置：
親ノード：(i – 1) ÷ 2（小数点以下切り捨て）
左の子ノード：2 * i + 1
右の子ノード：2 * i + 2
例：インデックス3のノードの親は(3-1)÷2 = 1、左の子は7、右の子は8
この計算式により、ポインタを一切使わずに木の親子関係をインデックス演算だけで表現できるため、メモリ効率が非常に高いのがヒープの利点です。
具体的なヒープ木の配列表現の例
最大ヒープ木と配列表現の例：
配列：[10, 8, 7, 5, 6, 3, 4]
インデックス0（10）→ 根
インデックス1（8）→ 10の左の子
インデックス2（7）→ 10の右の子
インデックス3（5）→ 8の左の子
インデックス4（6）→ 8の右の子
インデックス5（3）→ 7の左の子
インデックス6（4）→ 7の右の子
（すべての親が子より大きくヒープ条件を満たしている）
ヒープ木の基本操作と計算量
続いては、ヒープ木の基本操作と計算量を確認していきます。
| 操作 | 計算量 | 説明 |
|---|---|---|
| 最大値（最小値）の参照 | O(1) | 根のノードを見るだけ |
| 挿入（Insert） | O(log n) | 末尾に追加して上向き調整 |
| 最大値（最小値）の取り出し | O(log n) | 根を削除して下向き調整 |
| ヒープ構築（Build Heap） | O(n) | 全ノードに下向き調整を適用 |
上向き調整（Sift Up）の仕組み
要素を末尾に追加した後、親ノードと比較してヒープ条件を満たすまで上に移動させる操作を「上向き調整（Sift Up / Bubble Up）」と呼びます。
木の高さに比例してO(log n)回の比較・交換で完了します。
下向き調整（Sift Down）の仕組み
根を取り出した後、末尾要素を根に移動させ、子ノードの大きい方と比較しながら適切な位置まで降ろしていく操作が「下向き調整（Sift Down / Heapify）」です。
こちらもO(log n)の計算量で完了します。
まとめ
この記事では、ヒープ木とは何か、二分ヒープの構造と性質について、完全二分木・ヒープ条件・配列表現・インデックス計算・基本操作まで詳しく解説しました。
ヒープ木は完全二分木と配列表現の組み合わせにより、効率的なメモリ使用とO(log n)の操作性を実現する優れたデータ構造です。
今回の内容を参考に、ヒープ木の構造と操作をしっかり身につけていきましょう。
