データ構造のバイナリヒープ（二分ヒープ）とは？基本概念とMax Heap・Min Heapの違いを解説

ヒープ（Heap）、またはバイナリヒープ（二分ヒープ／Binary Heap）は、平衡二分探索木のデータ構造の一種であり、その特殊なケースにあたります。最大の特徴は、「完全二分木（Complete Binary Tree）」という構造を持っている点です。

完全二分木としての性質

完全二分木では、葉のレベルを l としたとき、l − 1 レベルまでのすべてのノードが埋まった状態になり、最後の l レベルにおいては、ノードが必ず左詰めで配置されるという規則があります。この厳密な構造により、配列を使って効率的にヒープを実装できるという利点が生まれます。

ヒープの順序性（ヒープ条件）

バイナリヒープでは、ルートノードのキー値が子ノードのキー値と比較され、一定の規則に従って配置されます。あるノード a が子ノード b を持つ場合、次の関係が成り立ちます。

key(a) ≥ key(b)

この条件は「親の値は常に子の値以上である」ことを意味します。このように親子間の大小関係が保たれることで、ツリー全体に秩序が生まれ、最大値や最小値の取得を高速に行えるようになります。

ヒープの2つの種類

親子間の大小関係の基準によって、ヒープは次の2種類に分類されます。

1. Max Heap（最大ヒープ）

親ノードの値が常に子ノードの値以上となるヒープです。この場合、ルートノードには必ずデータ全体の中で最大の値が格納されます。優先度付きキューなどで最大値を素早く取り出したい場合に活用されます。

2. Min Heap（最小ヒープ）

逆に、親ノードの値が常に子ノードの値以下となるヒープです。ルートノードには必ず最小の値が格納されます。ダイクストラ法などのアルゴリズムで最小コストの要素を繰り返し取り出す処理によく使われます。

Max Heap と Min Heap の例

以下は、それぞれ Max Heap と Min Heap の構造例を示した図です。

まとめ

バイナリヒープは「完全二分木」という整然とした構造と「親子間の大小関係」という順序条件を組み合わせた強力なデータ構造です。この2つの性質により、挿入・削除・最大値・最小値の取得といった操作を O(log n) の計算量で効率的に実行できます。ヒープソートや優先度付きキューなど、さまざまなアルゴリズムの基盤として広く利用されているため、しっかりと理解しておきましょう。