ヒープソートを理解する

「データ構造とプログラミング」で習ったヒープソートの実装の動きが理解できてないので、頑張って理解しようぜっていう取り組みです。まずは、C の実装を Go で書き直したやつです。

とりあえず、28行目の (n - 2) / 2 の計算が何を意図してるのかが分かってないです。あと、配列一つだけで処理してるので理解が追いついてない。というわけで、一旦愚直に実装して追っ付けで理解していこうと思います。
※配列と言ってますが Go なのでスライスです。

その前にヒープソートのざっくりした挙動ですが、次のようになります。

データをヒープに格納する（max-heapを使用）
ヒープのルート値が最大値なので
1. ヒープはルート値を取り出す処理を繰り返す
2. ルート値をソート済み配列の最大インデックスに格納する
3. ソート済み配列のインデックスをデクリメント（2.1に戻る）

ヒープとソート済み用の配列を別に用意した実装を行ってみたのがこちら。

愚直に書いただけあって、長い。。。。。

ヒープソートは数列を格納する配列自体にヒープを組み込んで数字の入れ替えだけでソートを行うのが通例なので、配列一つだけで処理するように変更する。手順は次のようになる。

実装してみました。

Heapsort 関数の二回目のループ周り（20-42行）が授業のサンプルコードと同じっぽいので関数にしてみます。

授業のコードにだいぶ近づいてきました。
次に気になるのは Heapsort 関数の引数の配列をヒープにできるんじゃないかというところです。それができたら同じになるはず。

そこでこの式 (n - 2) / 2 に戻るんですが、
今回のデータだとサイズが 10 なので計算すると値が 4 になります。元データの値をツリーにして見ると、値が 10 のノードのインデックスを指しています。

heap tree

これは葉ノードを持つノードのインデックスのうち一番大きい値を指してますね。
おそらくランダム値が入っている配列をヒープ配列にするときは、葉ノードを持つノードの一番大きいインデックスから 0 までデクリメントしながらヒープの削除時の整列を行っていくとヒープ配列にできるということだと思います。

ということで一応書き換えてみました。授業のコードとほぼ同じですが。

ということでヒープソートを（たぶん）理解できた！