ヒープソート
読み：ヒープソート
外語：heap sort
ヒープを利用したソート。最悪計算量はO(n log n)。
数列の並び方がどのようであっても、安定した処理時間を持つ。
ヒープソートの手順
1. ソートを始める前に配列をヒープ化する
87
│
┌───┴───┐
│ │
59 67
│ │
┌─┴─┐ ┌─┴─┐
│ │ │ │
50 38 54 29
│ │ │
┌┴┐ ┌┴┐ ┌┘
│ │ │ │ │
43 35 15 11 ８
2. 一番最初の節点(87)と一番最後の節点(8)の値を入れ替え, 一番最後
の節点の値はソート済みとする
８
│
┌───┴───┐
│ │
59 67
│ │
┌─┴─┐ ┌─┴─┐
│ │ │ │
50 38 54 29
│ │
┌┴┐ ┌┴┐
│ │ │ │
43 35 15 11 87
3. 木全体を再びヒープ化する
67
│
┌───┴───┐
│ │
59 54
│ │
┌─┴─┐ ┌─┴─┐
│ │ │ │
50 38 ８ 29
│ │
┌┴┐ ┌┴┐
│ │ │ │
43 35 15 11 87
4. 2.に戻る. 以下すべての節点がソート済みになるまで続ける.
11
│
┌───┴───┐
│ │
59 54
│ │
┌─┴─┐ ┌─┴─┐
│ │ │ │
50 38 ８ 29
│ │
┌┴┐ ┌┘
│ │ │
43 35 15 67 87
再検索