ヒープ

ヒープとは

ヒープとは、特定の順序制約を持つ木構造の一種です。具体的には、「親要素は子要素よりも常に大きいか等しい（最大ヒープ）」または「親要素は子要素よりも常に小さいか等しい（最小ヒープ）」というルールが適用されます。この制約により、ヒープは効率的なデータ管理を可能にし、特に最小値（または最大値）を高速に取り出す必要がある場合に有効です。

ヒープの概要

ヒープは、優先度付きキューの実装や、ダイクストラ法やプリム法といったグラフアルゴリズムで利用されます。ヒープにはさまざまな種類があり、それぞれ特徴が異なります。代表的なものには、二分ヒープ、二項ヒープ、フィボナッチヒープなどがあります。

ヒープの種類

• - 二分ヒープ (バイナリヒープ): 最も基本的なヒープで、完全二分木を使用します。挿入や削除が比較的容易で、実装も簡単です。
• - 二項ヒープ: 複数の二項木を組み合わせた構造を持ち、マージ操作が高速に行えます。
• - フィボナッチヒープ: 挿入や最小値検索、マージが償却時間で高速に行え、削除操作も効率的です。
• - その他のヒープ: 2-3ヒープ、Beap、D-aryヒープ、Leftistヒープ、Pairingヒープ、Skewヒープ、Softヒープ、Ternaryヒープなど、さまざまなバリエーションが存在します。

二分ヒープの詳細

構造

二分ヒープは、親要素が常に2つの子要素よりも大きくならない（またはその逆）ように構築された木構造です。この構造のおかげで、以下の特徴があります。

• - 挿入、削除: O(log n)の計算量で実行可能。
• - 探索: O(n)の計算量が必要で、全要素を調べる必要があるため、効率的ではありません。
• - 最小（または最大）要素: ルートが常に最小（または最大）の要素になります。

二分ヒープは、配列を使って効率的に実装できます。要素の添字が1から始まる場合、要素nの親は n ÷ 2、子は 2n および 2n + 1 で計算できます。0から始まる場合は、親が (n - 1) ÷ 2、子が 2n + 1 と 2n + 2になります。この特性により、ポインタを使わずに配列のみでヒープを表現できます。

実装

配列を使ってヒープを実装する際、要素の入れ替えでコピーの負荷が問題となる場合があります。この場合は、要素へのポインタまたは添字を格納した配列を別に作成し、そちらでヒープ構造を管理することで、コピーの負荷を軽減できます。

ヒープの操作

ヒープでは、主に以下の操作が行われます。

探索

ヒープは、子要素間の大小関係に制約がないため、任意の要素を探すには全要素を順に調べる必要があります。そのため、一般的な探索には適していません。

挿入

1. 新しい要素をヒープの末尾（配列の最後）に追加します。
2. 追加した要素を親要素と比較し、親要素よりも大きい（または小さい）場合は、親要素と入れ替えます。
3. この操作を、要素がルートに到達するか、親要素との比較で順序が正しくなるまで繰り返します。

削除

ルート（最小または最大要素）を削除する手順は以下の通りです。

1. ルート要素を削除し、ヒープの末尾の要素をルートに移動します。
2. ルートに移動した要素を、その子要素と比較します。
3. 子要素よりも小さい（または大きい）場合は、小さい（または大きい）方の子要素と入れ替えます。
4. この操作を、要素が葉に到達するか、子要素との比較で順序が正しくなるまで繰り返します。

ルート以外の要素を削除する場合は、削除する要素を末尾の要素で置き換えた後、上記の挿入または削除の手順を適用します。

まとめ

ヒープは、優先度付きキューやソートなどのさまざまなアプリケーションで利用される重要なデータ構造です。特に、最小値または最大値を効率的に取り出す必要がある場合に非常に有効です。二分ヒープはその中でも最も基本的な形であり、理解しておくことで、より複雑なデータ構造やアルゴリズムを学ぶ上で役立ちます。

もう一度検索