[解決済み] ヒープ構築のトップダウン・アプローチはボトムアップよりも成長度合いがO(n)よりもO(log n)低いにもかかわらず、なぜ効率が悪いのでしょうか？

質問

O(n)オーダーのヒープ構築のボトムアップ・アプローチはどのようなものですか？Anany Levitin は彼の著書で、これは O(log n) のオーダーを持つトップダウンアプローチよりも効率的であると述べています。なぜですか？

どのように解決するのですか？

タイプミスとしか思えません。

ヒープを構築するための標準的なアルゴリズムは2つあります。1つは空のヒープから始めて、一度に1つずつ繰り返し要素を挿入していくものである。各挿入にかかる時間はO(log n)なので、この手法によるヒープ構築のコストはO(n log n)と上限を設定できる。最悪の場合、逆ソートで要素を挿入すると、実行時間はΘ(n log n)になることが判明した。

もう1つのアプローチは、ヒープ化アルゴリズムで、各要素を独自のバイナリヒープで開始し、徐々に合体させることでヒープを直接構築するものである。このアルゴリズムは入力に関係なく、時間O(n)で実行される。

最初のアルゴリズムで時間Θ(n log n)を要するのは、挿入される要素の後半を見ると、それぞれ高さがΘ(log n)のヒープに挿入されているので、バブルアップを行うたびにコストが高くなる可能性があるからです。n / 2個の要素があり、それぞれが挿入するのにΘ（log n）の時間がかかるかもしれないので、最悪の場合の実行時間はΘ（n log n）です。

一方、heapifyアルゴリズムは、その時間の大半を小さなヒープでの作業に費やします。半分の要素は高さ0のヒープに、4分の1は高さ1のヒープに、8分の1は高さ2のヒープに挿入される、などです。つまり、作業の大部分は小さなヒープに要素を挿入することに費やされ、これは著しく高速です。