ヒープとは
ヒープとはデータ構造の一種であり、親要素が子要素よりも常に大きい（あるいは小さい）という特徴を持つ木構造です。つまり、ヒープの根が最大値（あるいは最小値）になり、$O(1)$ で参照することができます。またデータの挿入や最大値（あるいは最小値）の削除も $O(\log{N})$ と高速で可能なことから、優先度付きキューの実装としても利用されています。本記事では、特に二分木を使用した二分ヒープについて扱います。
ヒープ化にかかる計算量
ヒープ化されてない配列からヒープを作成する場合の計算量についてですが、1つのデータの挿入に $O(\log{N})$ 要することから考えると、直感的には $O(N\log{N})$ になりそうですが、実際には $O(N)$ で可能です。一例として、Python の heapq の実装にも線形時間でリストをヒープに変換するとの記述があります。
heapq — Heap queue algorithm — Python 3.10.1 documentation
Transform list x into a heap, in-place, in linear time.
$O(N)$ のヒープ化では、上記のように一つずつ値を挿入するのではなく、ヒープ化されていない配列に対してヒープの条件を満たすように値を交換していく（これが in-place に相当する）ことでヒープを作成します。
具体例を挙げながら見てみましょう。ここでは親ノードより子ノードが大きい条件を満たす、最大ヒープを作成します。
- 最も左にあるのが初期状態です。親ノードより子ノードが大きいという条件を満たしていません。ここから、ヒープの下の方から上の方へと順にヒープ条件を満たすように値を交換していきます。
- まず、最も深いノードである 2、6、4、7 については子のノードを持っていないので操作は必要はありません。
- 次に、値が 5 のノードとそれより下にあるノードがヒープの条件を満たすように値を交換します。ここでは、5 と 7 を交換します。これにより、親が 7 で子が 4 と 5 になり、ヒープ条件を満たしました。
- 同様に 1 と 6 を交換することで、親が 6、子が 1 と 2 になりヒープ条件を満たします。
- 最後に、最も親のノードとそれより下にあるノードがヒープ条件を満たすように値を交換します。3 と 7、次いで 3 と 5 の値を交換することで全てのノードにおいてヒープ条件が満たされます。
この操作にかかる計算量を考えると、注目したノードとそれより下にあるノードがヒープ条件を満たすために、自分より下のノードの深さに比例する計算量が必要になります（詳細はここでは割愛しますが、heapq の実装1などを読むと理解できるはずです）そして深さに比例する計算量をその深さのノード数分だけ行うことになります。二分木の構造上、深さの浅いノードが大半を占めるので、感覚的にも $O(N\log{N})$ かからなそうな気がしてきましたね。
一般化してみましょう。
まず、必要な式変形を確認します。$|x|<1$ を満たす場合の無限等比級数の和と、その微分は以下のように表されます。
\sum_{j=0}^{\infty}x^j = \frac{1}{1-x}
\sum_{j=0}^{\infty}jx^{j-1} = \frac{1}{(1-x)^2}
微分した式に $x$ をかけると以下の式が得られます。
\sum_{j=0}^{\infty}jx^{j} = \frac{x}{(1-x)^2}
これを利用すると、ヒープ化に必要な計算量は以下のようになります。ここでは、高さ（深さ）を $h = \lfloor \log{N} \rfloor$ と定義します。（$\lfloor \ \rfloor$ は floor 関数で、小数点以下を切り捨てます）
\begin{align}
\sum_{j=0}^{h}j \cdot 2^{h-j} &= 2^h \sum_{j=0}^{h}\frac{j}{2^j} \\
&\leq 2^h \cdot 2 \\
&\in O(N)
\end{align}
このようにしてヒープ化は $O(N)$ で計算できることが確認できました。
ヒープソートにかかる計算量
ヒープ化は $O(N)$ で可能ですが、あくまでヒープはソートとは異なり、最大値（あるいは最小値）を取り出すことしかできません。そのためヒープを利用してソートを行うヒープソートでは、$O(\log{N})$ の取り出しを $N$ 回行う必要があり、計算量が $O(N\log{N})$ になる点には注意が必要です。
まとめ
- ヒープ化は、ヒープの下から上へと順にヒープ条件を満たすように値を交換することで、$O(N)$ で計算できる。
- ヒープソートはあくまで $O(N\log{N})$ 要する。