ヒープへの挿入の時間計算量

1. 概要

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

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

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

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

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

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

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

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

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

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

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

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

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