ソートのアルゴリズムについて勉強しています。
一般社団法人ソフトウェアエンジニアリング協会の勉強会に参加させてしています。
そこでは、コンピュータサイエンスの基礎を勉強しています。
ソートのアルゴリズムについて勉強していたのですが、ヒープソートについて勘違いからつまづいていたので、それをまとめておきます。
まずヒープについて、最大ヒープ（親＞＝子）もしくは最小ヒープ（親＜＝子）の関係が成り立つ二分木です。
最初誤解していましたが、左の子の値と、右の子の値の大小関係は不問（どちらでも良い）です。
クイックソートのアルゴリズム
以下の配列を降順にソートするとします。
[4, 10, 3, 5, 1]
4
/ \
10 3
/ \
5 1
まず上記の二分木を最大ヒープ（親>=子）となるように並び替えます。
子ノードを持っているのは、10と4です。
まず10について、子ノード（5と1）と比較します。この時、2つの子ノードの大きい方と比較します。なので10と5を比較して、10の方が大きいのでそのまま。
次に、4について、子ノード（10と3)と比較します。大きい方と比較するので、4と10を比較して、10の方が大きいので、4と10を入れ替えます。
10
/ \
4 3
/ \
5 1
これで完成と言いたいところですが、一度沈んだ4をさらに沈める必要が�るか確かめる必要があります。
（入れ替えが起きたら、その先も崩れている可能性があるからです）
4について、子ノード（5と1）と比較します。大きい方と比較するので、4と5を比較して、5の方が大きので4と5を入れ替えます。
10
/ \
5 3
/ \
4 1
これで、最大ヒープの完成です。
次に、頂点（ルート）である10と最後の子ノードの要素を入れ替えます。
1
/ \
5 3
/ \
4 10
※私は最初、勘違いしていました。どうしてわざわざ、最後のこノードと入れ替える必要があるのでしょうか？
そもそもこのヒープは、配列として操作していることを忘れてはいけません。
[10, 5, 3, 4, 1] → [1, 5, 3, 4, | 10]
[ 未確定ヒープ | 確定済み（ソート済み） ]
挿入ソートや選択ソートの場合は、配列の右側から確定済み（ソート済み）になっていましたが、ヒープソートの場合は右から確定済みとします。
なので、未確定ヒープの最後の要素と交換する必要があります。
私がしていた勘違い
10
/ \
5 3
/ \
4 1
ここから、10を取り出して、別の場所に保管するイメージ
?
/ \
5 3
/ \
4 1
この時、?には何を入れるべきか？ 直下の子ノード(5か3）を昇格させても良いのでは？と考えていました。
（これは誤りです）
挿入ソートや選択ソートは配列の中でやり取りするイメージがついていたのですが、ヒープソートはヒープを扱っているイメージを持っていました。
ヒープソートでも、やっていることは配列の順序を並び替えることです。
さて、末尾の10は確定したので、入れ替えたヒープについて、同様に操作していきます。
1
/ \
5 3
/ \
4 10
子ノードを持っているのは、1と5です。
5について、子ノード（4）と比較します。5と4を比較して、5の方が大きのでそのまま。
次に、1について、子ノード（5と3）と比較します。大きい方と比較するので、1と5を比較して、5の方が大きので1と5を入れ替えます。
5
/ \
1 3
/ \
4 10
入れ替えが起きたので、1をさらに沈める必要があるかを確認します。
1と4 を比較して、4の方が大きいので、1と4を入れ替えます。
5
/ \
4 3
/ \
1 10
これで最大ヒープの完成です。
5と未確定ヒープの最後のノードの1を入れ替えます。
1
/ \
4 3
/ \
5 10
[1, 5, 3, 4, | 10] → [1, 4, 3, | 5, 10]
[ 未確定ヒープ | 確定済み（ソート済み） ]
さて、末尾から2つ目の要素までは確定したので、入れ替えたヒープについて、同様に操作していきます。
子ノードを持っているのは、1です。
1について、子ノード(4と3）と比較します。4の方が大きいので、1と4を入れ替えます。
4
/ \
1 3
/ \
5 10
これで最大ヒープが完成です。
4と未確定ヒープのサイドのノードの3と入れ替えます。
3
/ \
1 4
/ \
5 10
[1, 4, 3, | 5, 10] →[3, 1, | 4, 5, 10]
[ 未確定ヒープ | 確定済み（ソート済み） ]
さて、末尾から3つ目の要素までは確定したので、入れ替えたヒープについて、同様に操作していきます。
子ノードを持っているのは、3です。
3と1を比較して、3の方が大きいのでそのまま。
これで最大ヒープが完成です。
3と未確定ヒープの最後のノードの1を入れ替えます。
[3, 1, | 4, 5, 10] → [1, | 3, 4, 5, 10]
[ 未確定ヒープ | 確定済み（ソート済み） ]
未確定ヒープが残り1つになりました。当然、ルートの1は子ノードを持っていないので、これがそのまま確定です。
[1, | 3, 4, 5, 10] →[| 1, 3, 4, 5, 10]
[ 未確定ヒープ | 確定済み（ソート済み） ]
以上で、ヒープソートを使って、配列の要素を昇順に並び替えることができました。