二分ヒープの配列表現を徹底解説！最小ヒープ・最大ヒープの違いとインデックス計算法

ヒープ順序の性質を満たす完全二分木のことを二分ヒープ（バイナリヒープ）と呼びます。二分ヒープは、優先度キューやヒープソートなど、多くのアルゴリズムの基礎となる重要なデータ構造です。

二分ヒープの種類

ノード間の大小関係に基づいて、二分ヒープは次の2種類に分類されます。

最小ヒープ（Min Heap）

各ノードの値が、必ず親ノードの値以上になるようなヒープです。この性質により、根（ルート）ノードには常に木全体の中で最も小さい値が格納されます。

最大ヒープ（Max Heap）

各ノードの値が、必ず親ノードの値以下になるようなヒープです。根ノードには常に木全体の中で最も大きい値が格納されます。

二分ヒープの配列表現の基本ルール

二分ヒープの要素は通常、配列を使って表現されます。木構造をポインタではなく配列だけで管理できるため、メモリ効率が高く、アクセスも高速という利点があります。

配列表現における基本的なルールは以下の通りです。

• 根（ルート）要素のインデックスは 0 です。
• あるノードのインデックスを i とするとき、それに関連するノードのインデックスは次の式で求められます。
  • 左の子：(2 × i) + 1
  • 右の子：(2 × i) + 2
  • 親：(i − 1) ÷ 2（小数点以下は切り捨て）

これらの規則に従えば、木の形状を意識することなく、ヒープを一次元の配列として簡単に扱うことができます。以下はその一例です。

最小ヒープの具体例

最小ヒープでは、根ノードが最小値を持ち、すべてのノードの値が親ノード以上になります。上記の配列の場合、先頭の「1」が根であり、以降の要素も親子関係の順序制約を満たしています。

配列表現：

最大ヒープの具体例

最大ヒープでは、根ノードが最大値を持ち、すべてのノードの値が親ノード以下になります。次の配列では、先頭の「11」が根となり、値が降順方向に配置されていることがわかります。

配列表現：

まとめ

二分ヒープは、完全二分木を配列で効率的に表現できるのが大きな特徴です。インデックスの計算式さえ覚えてしまえば、子や親へのアクセスはO(1)で行えるため、実装もシンプルになります。優先度キューやヒープソートを実装する際には、ぜひこの配列表現の考え方を活用してください。