ヒープソート

ヒープソートは最悪計算時間が$O\left(n\log \right(n\left)\right)$になる非安定ソートです。 手順はヒープを作ることと、そのヒープから最大値または最小値を取り出すことでできます。

上の木構造を作ってしまえばあとは繰り返しの作業です。 2. 9が最大なのは明らかなので、9を取り出します。 3. 9を取り出したら末尾の小さい数を一つ 1, 2, 3より9があったところに持ってきて、再度上が大きく下が小さくなるようなグラフを作ります。 4. そうすると再度最も大きい値が頂点に来ます。(今回なら5) あとは2.以降の繰り返しになります。