プログラミングやアルゴリズムを学ぶ上で「ヒープ」というデータ構造は欠かせない知識のひとつです。
「ヒープって名前は聞いたことあるけど、どういう構造なの？」と疑問をお持ちの方も多いのではないでしょうか。
この記事では、ヒープとは何か、データ構造としての意味と仕組みについて、二分ヒープ・最大ヒープ・最小ヒープ・優先度付きキューとの関係まで詳しく解説しています。
データ構造の基礎を固めたい方はぜひ参考にしてください。
ヒープとは？データ構造としての基本的な意味と定義
それではまず、ヒープの基本的な意味と定義について解説していきます。
ヒープとは、完全二分木という木構造をベースに持ち、親ノードが常に子ノード以上（または以下）の値を持つという「ヒープ条件」を満たすデータ構造のことです。
コンピュータサイエンスにおけるヒープは、最大値または最小値を素早く取り出すことに特化した、優先度付きキューの実装に使われることが多いデータ構造です。
なお、プログラミングにおけるメモリ領域としての「ヒープ（heap領域）」とは異なる概念です。
完全二分木とはどういう構造か？
ヒープのベースとなる「完全二分木」とは、最下層を除くすべての層がノードで埋まっており、最下層のノードは左から順に詰まっている二分木のことです。
この構造のおかげで、ヒープは配列（1次元のリスト）で効率よく表現することができます。
配列でのヒープ表現では、インデックスiの親ノードは(i-1)÷2、左の子ノードは2i+1、右の子ノードは2i+2で計算できます。
配列でのヒープ表現の例（最大ヒープ）：
配列：[9, 7, 5, 3, 6, 2, 4]
インデックス0（9）→ 根
インデックス1（7）→ 9の左の子
インデックス2（5）→ 9の右の子
インデックス3（3）→ 7の左の子
インデックス4（6）→ 7の右の子
最大ヒープと最小ヒープの違い
ヒープには最大ヒープと最小ヒープの2種類があります。
| 種類 | ヒープ条件 | 根（ルート）の値 | 主な用途 |
|---|---|---|---|
| 最大ヒープ | 親 ≥ 子（親は子以上の値） | 全体の最大値 | 最大値の高速取得・ヒープソート |
| 最小ヒープ | 親 ≤ 子（親は子以下の値） | 全体の最小値 | 優先度付きキュー・ダイクストラ法 |
ヒープの主な操作と計算量を解説
続いては、ヒープの主な操作と計算量を確認していきます。
ヒープはいくつかの基本的な操作を効率よく行えることが特徴です。
挿入操作（Insert）の仕組み
ヒープへの要素の挿入は次の手順で行います。
まず新しい要素を配列の末尾に追加し、次に親ノードと比較しながら適切な位置まで上昇させる「上向き調整（Sift Up）」を行います。
挿入操作の計算量はO(log n)であり、木の高さに比例した効率的な操作です。
最大値（または最小値）の取り出し操作の仕組み
ヒープの最大の特徴は、最大値（最大ヒープの場合）を常にO(1)で参照できることです。
取り出し（削除）の場合は根を取り出した後、末尾要素を根に移動させ、下向き調整（Sift Down）でヒープ条件を回復します。
取り出し操作の計算量はO(log n)です。
ヒープの構築（Build Heap）の計算量
n個の要素からヒープを構築する際、単純に1要素ずつ挿入するとO(n log n)かかりますが、末尾の親ノードから順に下向き調整を行う「一括構築」ではO(n)で実現できます。
これはヒープソートやヒープを使うアルゴリズムの効率化に重要な性質です。
優先度付きキューとしてのヒープの活用
続いては、優先度付きキューとしてのヒープの活用を確認していきます。
ヒープの最も代表的な応用が「優先度付きキュー（Priority Queue）」の実装です。
優先度付きキューとは、通常のキュー（先入れ先出し）と異なり、優先度の高い要素から取り出せるデータ構造です。
最小ヒープを使うことで、常に優先度が最も高い（値が最小の）要素をO(log n)で取り出せる優先度付きキューを実装できます。
ダイクストラ法でのヒープの活用
グラフの最短経路を求めるダイクストラ法では、次に処理すべき最小コストのノードを効率よく取り出すために最小ヒープ（優先度付きキュー）が使われます。
ヒープを使うことでダイクストラ法の計算量をO((V+E) log V)（Vは頂点数、Eは辺数）に抑えることができます。
Pythonのheapqモジュールでのヒープ活用例
Pythonでのヒープ（最小ヒープ）の使用例：
import heapq
heap = []
heapq.heappush(heap, 5) # 要素の挿入
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
print(heapq.heappop(heap)) # 最小値1を取り出す
まとめ
この記事では、ヒープとは何か、データ構造としての意味と仕組みについて、二分ヒープ・最大ヒープ・最小ヒープ・優先度付きキューへの応用まで詳しく解説しました。
ヒープは最大値・最小値を効率よく取り出せるデータ構造であり、ソートや最短経路探索など多くのアルゴリズムの基盤となっています。
今回の内容を参考に、ヒープの仕組みと活用方法をしっかり身につけていきましょう。
