以下、根ノードからの個別の沈降調整は、葉ノードを走査しないことも述べています。
時間複雑度の概念の問題から、実際には 2 つのオブジェクトを比較するときに時間複雑度が不明瞭になることがあります。例えば、A の時間複雑度は O (n/2) であり、B の時間複雑度は O (n) です。教科書の概念では係数を取り除く必要があるため、A と B の時間複雑度は同じになりますが、実際には賢明な人は A を選択するでしょう。なぜなら、A には 2 以外の n が含まれており、時間複雑度が少し低くなるからです。
したがって、より明確に計算するために、次に時間複雑度を計算するプロセスがより詳細になります。
最初に、根ノードから個別に下降調整を行う必要があり、配列内のすべての非葉ノードを走査する必要があります。ノードが n 個ある場合、すべての非葉ノードは n/2 個あり、したがって時間複雑度は O (n/2) です。
次に、下降調整中に、各ノードは最低でも下降する必要がなく、最大で木の深さまで下降する必要があります。木の深さは logn です。したがって、各ノードの下降の時間複雑度は O (logn/2) です。
したがって、根ノードから個別に下降調整を行う総時間複雑度は O ((n/2)*(logn/2)) です。
次に、最後の非葉ノードから個別に下降調整を行う時間複雑度を計算します。同様に、すべての非葉ノードの数は n/2 であり、時間複雑度は O (n/2) です。
次に、下降調整中に、各ノードは最低でも下降する必要がなく、最大で木の深さまで下降する必要があります。木の深さは logn です。
したがって、各ノードの下降の時間複雑度も O ((n/2)*(logn/2)) です。
実際には、最後の非葉ノードから個別に下降調整を行う場合と根ノードから個別に下降調整を行う場合の時間複雑度は、簡略化された結果としてどちらも O (nlogn) です。したがって、時間複雑度の観点からは、本質的な違いはありません。
上記は、本書を読んでいる際に引き起こされたいくつかの考えと洞察です。必ずしも正確ではないかもしれませんが、読者の皆さんとの議論を歓迎します！一緒に学び、進歩しましょう。