ヒープソートのアルゴリズム

ヒープとは

　配列ar[0]...ar[N-1]を考えましょう。配列は各要素が線型に並んだ集合です。ここで配列の各要素をnode（ノード/節）と呼ぶことにします。i番目のnode ar[i]に対してar[2*i+1]とar[2*i+2]の2つのnodeをar[i]の「子」、ar[i]を子nodeの「親」と呼びましょう（fig-01）。

fig-01

　この対応付けによって、配列の各要素はar[0]をroot（ルート/根）としてその子node、さらにその子node……のように漏れ/重複なくたどることができます（fig-02）。

fig-02

　つまりこの線型な要素の並びは二分木（BinaryTree）と見立てることができるわけです（fig-03）。

fig-03

　さて、ここで「木の中にある各節について、親は子より小さくない（親 >= 子）」という条件を与えます。この条件を満たした例を fig-04 に示します。この条件:「親は子より小さくない」を満たした木をheap（ヒープ）と呼びましょう。

fig-04

ヒープに要素を追加する

　fig-04で示すヒープに要素を追加する方法を考えます。このヒープの末尾、すなわち配列の末尾に要素「9」を追加しました（fig-05）。

fig-05

　追加した要素がその親（ここでは「7」）より大きくなければヒープの条件を満たすので要素の追加はこれで完了です。ところがここで追加した要素「9」は親より大きく、ヒープの条件を満たしません。そこで追加した要素「9」とその親「7」とを交換します（fig-06）。

fig-06

　処理はこれで終わりではありません。親子の交換によって親の値が変化したのですから、さらにその上の親との間でヒープ条件を満たすかを確認し、大小関係が壊れていたら（親 < 子なら）交換しなければなりません。この処理を親子の大小関係が整うまで繰り返します（fig-07）。

fig-07