二分ヒープ

二分ヒープ(バイナリヒープ)とは



二分ヒープは、二分木をベースにした特殊なデータ構造であり、以下の二つの重要な制約を満たすことで特徴づけられます。

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)の計算量がかかります。マージ処理が頻繁に行われる場合は、二項ヒープのような別のヒープ構造を検討する方が良い場合があります。

まとめ



二分ヒープは、効率的なデータ管理を可能にする強力なデータ構造です。そのシンプルな構造と優れた性能から、多くの場面で利用されています。

もう一度検索

【記事の利用について】

タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。

【リンクついて】

リンクフリーです。