1. 概要

Heap は、特殊なタイプのバランスの取れた二分木データ構造です。 ヒープでの非常に一般的な操作はheapifyです。これは、そのプロパティを維持するためにヒープを再配置します。

このチュートリアルでは、heapify操作の変形であるmax-heapifyについて説明します。バイナリツリーでmax-heapify操作を実行する方法について、いくつかの例を使用して詳細に説明します。

2. ヒープの定義

ヒープまたはバイナリヒープは、完全なバイナリツリーであり、ヒーププロパティと呼ばれるいくつかの追加のプロパティがあります。 ヒーププロパティにジャンプする前に、ヒープにはmax-heapとmin-heapの2つのバリアントがあることに注意してください。ヒーププロパティはバリアントごとに少し異なります。

まず、max-heapのヒーププロパティについて説明します。 ヒーププロパティによると、ヒープ内の各ノードのキーまたは値は常にその子ノードよりも大きく、ルートノードのキーまたは値は常にヒープツリー内で最大です。

min-heapのheapプロパティは、各子ノードの値またはキーが常にその親ノードよりも大きく、ルートノードの値が常にヒープ内で最小であることを示しています。

いくつかの例を見てみましょう:

最初のツリーでは、ルートノードはツリー内の他のすべてのノードの中で最も価値の高いキーノードです。 また、すべてのサブツリーで、各親ノードは子ノードよりも大きな値のキーを持っています。 したがって、max-heapプロパティに従います。

2番目の例では、ルートノードはツリー内の他のすべてのノードの中で最小です。 また、このヒープのサブツリーの各親の値は、子ノードよりも小さいことがわかります。 したがって、min-heapプロパティを満たします。

3. 最大ヒープ操作

Max-heapifyは、ノードがmax-heapプロパティに従うように、ノードを正しい順序で配置するプロセスです。 最初に擬似コードを見てから、各ステップについて詳しく説明します。

入力としてノードの配列とインデックスを取ります。 変数andは、開始ノードの左右の子ノードを示します。

次に、max-heapプロパティを満たすように、入力配列からノードとそのサブツリーを配置します。

を使用して、最大ヒープを構築します。 ツリーの最下位レベルにあり、子ノードを持つノードからアルゴリズムを開始します。次に、max-heapプロパティに従って現在のノードとその子ノードを配置します。

この手順を完了すると、このプロセスを続行し、すべてのサブツリーがmax-heapプロパティに従っていることを確認します。このように、再帰的に呼び出してルートノードに戻り、ツリーがmax-heapプロパティ。

次に、入力配列からヒープを構築する方法を見てみましょう。 入力配列がheapプロパティに従わない場合は、ヒープを構築するために呼び出してから、構築されたヒープツリーで実行します。

4. Max-Heapifyの例

入力配列を取りましょう。 最初のステップは、配列からバイナリツリーを作成することです。

次に、最下位レベルのサブツリーを取得し、それがmax-heapプロパティに準拠しているかどうかのチェックを開始します。

ご覧のとおり、サブツリーはmax-heapプロパティに従いません。 ここで、親ノードには子ノードよりも大きな値が含まれている必要があります。 したがって、ツリーがmax-heapプロパティに従うようにするために、子ノードと親ノードの間でキー値を交換します。

続けて、最下位レベルから最上位レベルまでのすべてのサブツリーを調べてみましょう。

このサブツリーはmax-heapプロパティに従い、ここでは何も変更する必要はありません。 次に、右側のブランチを見てみましょう。

この場合も、サブツリーはmax-heapプロパティに従います。 このプロセスを続けましょう:

ここでも、ルートノードのキー値がツリー内のすべてのノードの中で最大ではないことがわかります。 したがって、ルートノードのキー値をその右の子ノードのキー値と交換して、max-heapプロパティと一致させました。

ここで、スワップ後、ルートノードから正しいサブツリーをチェックして、それがmax-heapプロパティに従っているかどうかを確認する必要があります。

最後に、ツリー全体をチェックして、max-heapifyプロパティを満たしているかどうかを確認してから、最終的なmax-heapツリーを取得します。

5. 結論

このチュートリアルでは、バイナリヒープでのmax-heapifyのプロセスについて説明しました。 また、入力配列から最大ヒープがどのように作成されるかを示す例も示しました。