1. 概要

ヒープは、一般的なツリーベースのデータ構造です。 ヒープでの一般的な操作は、新しいノードを挿入することです。

このチュートリアルでは、 新しいノードをヒープに挿入する方法について説明します。 また、挿入プロセスの時間計算量分析についても説明します。

2. 挿入アルゴリズム

最初にヒープ内の挿入アルゴリズムを見てから、手順について詳しく説明します。

入力は、配列、ヒープのサイズ、および挿入する新しいノードで構成されます。 親ノードを表すために使用します。 最初に、新しいノードを追加するためにヒープ内にスペースを作成します。新しい要素は最初にヒープの最後に追加されます。

新しく挿入されたノードがヒーププロパティを歪める可能性があります。確認するために、ヒープ化プロセスを実行します。 Heapify操作は、各サブツリーをボトムアップ方式でチェックし、それがheapプロパティに従っていることを確認します。

heapifyプロセスでは、ノードの値をその親の値と比較します。 それらが正しい順序になっていない場合は、ヒープのタイプ(最大または最小ヒープ)に基づいてそれらを交換します。

ここでは、挿入プロセスを要約した形式で示します。

3. 時間計算量分析

max-heapに新しいノードを挿入し、新しく挿入されたノードの親のキー値が新しく挿入されたノードのキー値よりも大きいシナリオを考えてみましょう。 このような場合、何もする必要はなく、ヒーププロパティに従うため、max-headを変更する必要はありません。

これは、ヒープに新しい要素を挿入する場合の最良の例です。 このような場合、挿入に必要な時間はになります。

最悪の場合、ヒーププロパティを維持するために、新しく挿入されたノードを下からルートノードまで各レベルで交換する必要があります。 これで、ヒープツリーがバランスの取れた完全なツリーデータ構造であることがわかりました。

最悪の場合、ツリーの各レベルで1つのスワップが必要です。 したがって、スワップの総数は、ヒープツリーのheightに等しくなります。 ノード数のあるバランスの取れた完全なツリーの高さはです。 各スワップには時間がかかります。

したがって、最悪の場合、ヒープにノードを挿入する時間計算量はになります。

4. 結論

このチュートリアルでは、ヒープ挿入アルゴリズムについて説明しました。 また、挿入アルゴリズムの時間計算量分析についても説明しました。