hello-algo/ja/docs/chapter_heap/build_heap.md

ヒープ構築

場合によっては、リスト内のすべての要素を使ってヒープを構築したいことがあります。この過程を「ヒープ構築」と呼びます。

ヒープへの挿入操作による実現

まず空のヒープを作成し、次にリストを走査して、各要素に対して順に「ヒープへの挿入操作」を実行します。つまり、要素をヒープの末尾に追加してから、その要素に対して「下から上へ」のヒープ化を行います。

要素が1つヒープに挿入されるたびに、ヒープの長さは1増加します。ノードは上から下へ順に二分木へ追加されるため、ヒープは「上から下へ」構築されます。

要素数を n とすると、各要素のヒープへの挿入操作には O(\log{n}) の時間がかかるため、このヒープ構築法の時間計算量は O(n \log n) です。

走査によるヒープ化で実現

実際には、より効率的なヒープ構築法を実現でき、全体は2つの手順に分かれます。

1. リストのすべての要素をそのままヒープに追加します。この時点では、ヒープの性質はまだ満たされていません。
2. ヒープを逆順で走査し（レベル順走査の逆順）、各非葉ノードに対して順に「上から下へ」のヒープ化を実行します。

あるノードをヒープ化するたびに、そのノードを根とする部分木は合法な部分ヒープになります。また、逆順で走査するため、ヒープは「下から上へ」構築されます。

逆順走査を選ぶのは、この方法なら現在のノードの下にある部分木がすでに合法な部分ヒープであることを保証でき、そのうえで現在のノードをヒープ化してはじめて有効になるからです。

なお、葉ノードには子ノードがないため、それ自体が自然に合法な部分ヒープであり、ヒープ化は不要です。以下のコードが示すように、最後の非葉ノードは最後のノードの親ノードであり、そこから逆順に走査してヒープ化を実行します。

[file]{my_heap}-[class]{max_heap}-[func]{__init__}

計算量の分析

以下では、2つ目のヒープ構築法の時間計算量を求めてみましょう。

• 完全二分木のノード数を n とすると、葉ノード数は (n + 1) / 2 です。ここで / は切り捨て除算を表します。したがって、ヒープ化が必要なノード数は (n - 1) / 2 です。
• 上から下へのヒープ化の過程では、各ノードは最大で葉ノードまでヒープ化されるため、最大反復回数は二分木の高さ \log n です。

上の2つを掛け合わせると、ヒープ構築過程の時間計算量は O(n \log n) となります。しかし、この見積もりは正確ではありません。二分木では下層のノード数が上層よりはるかに多いという性質を考慮していないためです。

次に、より正確な計算を行います。計算を簡単にするため、ノード数が n 、高さが h の「満二分木」を仮定します。この仮定は計算結果の正しさに影響しません。

上図に示すように、ノードを「上から下へヒープ化」する最大反復回数は、そのノードから葉ノードまでの距離に等しく、この距離こそが「ノードの高さ」です。したがって、各層の「ノード数 \times ノードの高さ」を合計すれば、すべてのノードのヒープ化反復回数の総和が得られます。

T(h) = 2^0h + 2^1(h-1) + 2^2(h-2) + \dots + 2^{(h-1)}\times1

上式を簡約するには中学の数列の知識を用います。まず T(h) に 2 を掛けると、次のようになります。

\begin{aligned}
T(h) & = 2^0h + 2^1(h-1) + 2^2(h-2) + \dots + 2^{h-1}\times1 \newline
2 T(h) & = 2^1h + 2^2(h-1) + 2^3(h-2) + \dots + 2^{h}\times1 \newline
\end{aligned}

ずらして引く方法を用い、下式の 2 T(h) から上式の T(h) を引くと、次が得られます。

2T(h) - T(h) = T(h) = -2^0h + 2^1 + 2^2 + \dots + 2^{h-1} + 2^h

上式を見ると、T(h) は等比数列であることがわかるため、和の公式を直接用いて、時間計算量は次のように求められます。

\begin{aligned}
T(h) & = 2 \frac{1 - 2^h}{1 - 2} - h \newline
& = 2^{h+1} - h - 2 \newline
& = O(2^h)
\end{aligned}

さらに、高さ h の満二分木のノード数は n = 2^{h+1} - 1 であるため、計算量は容易に O(2^h) = O(n) とわかります。以上の導出は、入力リストからヒープを構築する時間計算量が O(n) であり、非常に効率的であることを示しています。