ヒープソート

ヒープ構造の２分木の考え方を応用したソーティング方法。データ構造としては配列で表現する。（本来、配列化されたデータがソーティング対象）

ヒープとは

• 親＞子の構造を持つ２分木
• 子（兄弟）間の位置関係は自由（特に左右のルールなし。２分探索木とは異なる）

配列構造で２分木を表現

モデルとなる木へのデータ格納順は横型とする。よって、任意の要素（ノード） a[i] について

• 親：a[(i-1)/2]
• 子（左）：a[i×2+1]
• 子（右）：a[i×2+2 ]

の関係が成立する（剰余は切り捨て）

ヒープ化

• 末尾を含む部分木からヒープ化
• 先頭に向かってヒープ部分木を拡大して構成（大きい値の子と交換していけば良い）
• 最終的に全体がヒープ化される

ソーティングの考え方

ヒープ化されている２分木が対象

1. ソート対象の配列の末尾とルートを交換（末尾に来たルートはソート済み状態）
2. もし、1の後、木の状態がヒープでないなら再ヒープ化を行う（交換されたルートを適切な位置へ移動。大きい値の子と交換していけば良い）
3. 全体がヒープ化されていれば1へ戻る（再びルートを末尾と交換、、、、を繰り返す）

サンプルプログラムの解説