ヒープ構築のトップダウン手法は、成長の順番が低いにもかかわらず、ボトムアップより効率が低いのはなぜですかO（n）？

Question

オーダーO（n）のヒープ構築のボトムアップアプローチはどのようになっていますか？ Anany Levitinは、彼の本では、注文O（log n）であるトップダウンアプローチと比較して、これがより効率的であると述べている。どうして？

Answer 1

私はそれが誤字のようです。

ヒープを構築するための2つの標準アルゴリズムがあります。最初は、空のヒープから始め、繰り返し要素を1つずつ挿入します。個々の挿入には時間がかかる（log n）ので、このスタイルのヒープ構築のコストをO（n log n）で上限にすることができます。最悪の場合、ランタイムはΘ（n log n）であることが判明しました。逆ソート順に要素を挿入すると発生します。

もう1つのアプローチは、heapifyアルゴリズムです。ヒープアルゴリズムは、独自のバイナリヒープ内の各要素から開始し、順番にそれらをまとめてヒープを直接構築します。このアルゴリズムは、入力に関係なく時間O（n）で実行されます。

最初のアルゴリズムが時間を必要とするのは、Θ（n log n）の理由は、挿入される要素の後半部分を見ると、それぞれが高さのあるヒープに挿入されていることがわかりますΘ（log n）であるため、各バブルアップを実行するコストが高くなる可能性があります。 n/2個の要素があり、挿入するにはそれぞれΘ（log n）の時間がかかる可能性があるため、最悪の場合のランタイムはΘ（n log n）です。

一方、heapifyアルゴリズムは時間の大部分を小さなヒープで処理します。要素の半分は高さ0のヒープに、四分の一は高さ1のヒープに、8は高さ2のヒープに挿入されます。これは、作業の大部分が小さなヒープに要素を挿入するのに費やされることを意味します。

Answer 2

あなたの基本的な操作であることをスワッピング考える場合 -

をトップダウン構造では、ツリーが最初に構築され、heapify機能がnodes.The最悪の場合に呼び出されたが取捨選択する（ログをn回交換しますツリーの高さがログnであるツリーの上端までの要素）を、すべてのn/2葉ノードについて計算する。これにより、O（n log n）の上限が得られます。

ボトムアップ構築では、最初のパスですべてのリーフノードが順番になると仮定しているため、heapifyはn/2ノードでのみ呼び出されます。各レベルでは、可能なスワップの数は増えますが、発生するノードの数は減少します。

例： リーフノードのすぐ上のレベルでは、 は、最大で1つのスワップを持つことができるn/4ノードを持っています。 親のレベルでは、 n/8ノードで最大2回のスワップが可能です。 合計で、ヒープのボトムアップ構築のための効率（O（n））を考え出します。