二分
ヒープは、二分木をベースにした特殊な
データ構造であり、以下の二つの重要な制約を満たすことで特徴づけられます。
1.
ヒープ特性 (Heap Property): 親ノードの値が、その子ノードの値以上(または以下)であるという制約です。これにより、最大
ヒープ(親≧子)と最小
ヒープ(親≦子)の2種類が存在します。
2.
形状特性 (Shape Property): 木は完全にバランスが取れているか、最下層を除いて完全に埋まっており、最下層のノードは左から順に配置されます。これにより、効率的な
配列実装が可能になります。
これらの特性を持つことから、二分
ヒープは「部分順序付き木」とも呼ばれます。
順序関係と比較
要素間の順序は、数値的な大小関係だけでなく、任意の比較関数によって定義できます。したがって、
ヒープに格納されるデータは必ずしも数値である必要はなく、順序付けが可能であればどのようなデータ型でも扱うことができます。
比較関数が数値的な「より大きい」に基づいている場合、その
ヒープは最大
ヒープと呼ばれ、ルートに最大値が配置されます。逆に、「より小さい」に基づいている場合は最小
ヒープと呼ばれ、ルートに最小値が配置されます。優先度付きキューでは、最小
ヒープを用いて小さい値に高い優先度を与えることが一般的です。
要素の追加 (Up-Heap)
ヒープに新しい要素を追加する際には、以下の手順で
ヒープ特性を維持します。
1. 新しい要素を
ヒープの最下層に追加します。
2. 追加した要素とその親ノードを比較し、順序が正しくなければ交換します。
3. 順序が正しくなるまで、親との比較と交換を繰り返します。
この操作は、木の高さに比例する時間計算量O(log n)で行えます。しかし、実際の挿入では平均的に数レベルしか移動しないことが多く、平均的にはO(1)の計算量で済むことが知られています。
例:
最大
ヒープに「15」を追加する。
[図] 初期状態: [11, 8, 9, 4, 6, 7] -> 15を追加する位置にX
[図] 15をXに入れる: [11, 8, 9, 4, 6, 7, 15]
[図] 15と8を入れ替え:[11, 15, 9, 4, 6, 7, 8]
[図] 15と11を入れ替え:[15, 11, 9, 4, 6, 7, 8]
ルートの削除 (Down-Heap)
ヒープからルート要素を削除する際には、以下の手順で
ヒープ特性を維持します。
1. ルート要素を
ヒープの最後の要素と交換します。
2. 最後の要素を削除します。
3. 交換した要素を、子ノードと比較し、順序が正しくなければ交換します。
4. 順序が正しくなるまで、子との比較と交換を繰り返します。
この操作も、木の高さに比例するO(log n)の計算量で行えます。
例:
最大
ヒープのルート「15」を削除する。
[図] 初期状態:[15, 11, 9, 4, 6, 7, 8] ->15を削除
[図] 15と末尾の8を入れ替え:[8, 11, 9, 4, 6, 7]
[図] 8と11を入れ替え:[11, 8, 9, 4, 6, 7] -> down-heapで8を適切な位置に移動
ルート以外の要素の削除
1. 削除対象が末端ノードなら削除して終了
2. 末端ノードを削除位置へ移動する
3. down-heap を行う
4. 必要に応じて up-heap も行う
値の更新
ヒープ内の要素の値を更新する際は、値が増加した場合はup-heap、減少した場合はdown-heapを行います。削除後に要素を追加することでも同様の効果が得られます。
計算量
二分
ヒープは、平均的な計算量だけでなく、最悪計算量もO(log n)で抑えることができます。しかし、定数項が小さいため、現実的には他の
ヒープ構造よりも高速な場合が多く、特にプリミティブ型を扱う場合には二分
ヒープが推奨されます。
配列による実装
二分
ヒープは、古典的な二分木
データ構造で実装することも可能ですが、
配列を用いることでより効率的に実装できます。二分木のノードを幅優先探索順に番号付けすると、以下のような規則性が生まれます。
- - あるノードの番号をnとすると
- - 左の子の番号は 2n
- - 右の子の番号は 2n + 1
- - 親の番号は floor(n / 2)
この規則性により、ポインタを使用せずに、
配列だけで
ヒープ構造を表現し、効率的に要素をたどることができます。この実装方法は、特に
ヒープソートで有効です。
配列を
ヒープの格納場所として再利用することで、in-placeなソートを実現できます。
スレッド木
二分木の実装では、親ノードへの参照がないため、要素の追加時に適切な挿入位置を見つけるのが難しい場合があります。これを緩和するために、スレッド木という
データ構造が用いられます。スレッド木では、末端の要素において、子要素への参照の代わりに、通りがけ順での先行要素と後続要素への参照を格納します。これにより、探索が効率化されます。
二分
ヒープは、以下のような様々な場面で応用されています。
- - 優先度付きキューの実装
- - ヒープソート
- - ダイクストラ法やA*アルゴリズムなどのグラフアルゴリズム
マージ処理
二分
ヒープのマージ処理は、同サイズの
ヒープ同士の場合、O(n)の計算量がかかります。マージ処理が頻繁に行われる場合は、二項
ヒープのような別の
ヒープ構造を検討する方が良い場合があります。
まとめ
二分
ヒープは、効率的なデータ管理を可能にする強力な
データ構造です。そのシンプルな構造と優れた性能から、多くの場面で利用されています。